Решение: Монеты на пути Робота
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо» Робот перемещается в соседнюю правую клетку, по команде «вниз» — в соседнюю нижнюю. Квадрат ограничен внешними стенами. Между соседними клетками квадрата также могут быть внутренние стены. Сквозь стену Робот пройти не может.
Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота.
Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. Исходные данные представляют собой электронную таблицу размером $N \times N$, каждая ячейка которой соответствует клетке квадрата. Внутренние и внешние стены обозначены утолщёнными линиями.
Решение по шагам
5 шаговРобот движется только вправо и вниз, поэтому в клетку можно попасть только из клетки сверху или из клетки слева, если между клетками нет стены.
Для каждой клетки строятся два значения: максимальная и минимальная сумма монет на допустимом пути от начальной клетки до этой клетки.
$$max[i][j] = a[i][j] + \max\limits_{(k,l)\to(i,j)} max[k][l]$$Аналогично минимальная сумма определяется через минимум по допустимым переходам.
$$min[i][j] = a[i][j] + \min\limits_{(k,l)\to(i,j)} min[k][l]$$Начальная клетка содержит свою монету. В каждой последующей клетке учитываются только переходы, не пересекающие внутреннюю стену.
$$max[1][1] = min[1][1] = a[1][1]$$После заполнения таблиц в правой нижней клетке находятся искомые значения.
$$max[N][N],\ min[N][N]$$В правой нижней клетке таблиц динамического программирования находятся два ответа: сначала max[N][N], затем min[N][N].
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Не учитывать монету в начальной или конечной клетке.
Разрешать переход через внутреннюю стену.
Использовать только один показатель вместо отдельных таблиц максимальных и минимальных сумм.
Перепутать порядок ответов: сначала требуется максимальная, затем минимальная сумма.