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