Решение: Минимальный и максимальный путь
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку; по команде вниз — в соседнюю нижнюю. Робот разрушается при попытке выхода за границу квадрата или при попытке пересечения стены клетки. В таблице стены отмечены границами с утолщением.
Перед запуском Робота в каждой клетке квадрата указан бонус, который Робот забирает после посещения клетки. Размер бонуса в каждой клетке — натуральное число, не превышающее 100. Это правило относится к начальной и конечной клеткам маршрута Робота.
Определите минимальную и максимальную суммы бонусов, которые может собрать Робот, перемещаясь из левой верхней клетки квадрата в его правую нижнюю клетку. Исходные данные представлены в форме электронной таблицы размером $N \times N$, в которой одна ячейка соответствует одной клетке квадрата. Стены, через которые Роботу нельзя проходить, отмечены в электронной таблице границами с утолщением.
Решение по шагам
5 шаговСоздайте для каждой клетки две величины: минимальную и максимальную сумму бонусов на пути из левой верхней клетки в эту клетку.
Для начальной клетки обе величины равны бонусу этой клетки.
$$F_{1,1}^{\min}=F_{1,1}^{\max}=a_{1,1}$$Для каждой следующей клетки рассмотрите переходы из клетки сверху и из клетки слева. Переход учитывается только тогда, когда между клетками нет стены.
$$F_{i,j}^{\min}=a_{i,j}+\min(F_{i-1,j}^{\min},F_{i,j-1}^{\min})$$Аналогично вычислите максимальную сумму, заменив минимум на максимум.
$$F_{i,j}^{\max}=a_{i,j}+\max(F_{i-1,j}^{\max},F_{i,j-1}^{\max})$$В правой нижней клетке получаются искомые минимальная и максимальная суммы. Запишите их в указанном порядке.
Числовой ответ зависит от данных электронной таблицы, приложенной к заданию.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Не учитывают бонус начальной или конечной клетки.
Разрешают переход через стену.
Рассматривают только один из возможных маршрутов.
Меняют порядок записи минимальной и максимальной суммы.