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