Что проверяет задание

Дана прямоугольная таблица чисел. Нужно найти маршрут с особым свойством: обычно максимальную или минимальную сумму, иногда количество маршрутов. Двигаться разрешено только указанными шагами.

Определения

Таблица (решётка), клетки (i, j) со значениями. Маршрут, последовательность соседних клеток по разрешённым ходам.

Разрешённый ход, типично вправо и вниз, иногда ещё вниз-вправо по диагонали, влево или вверх. Множество ходов задаёт, из каких клеток вообще можно дойти до конца.

Стоимость маршрута, чаще сумма чисел в посещённых клетках. Иногда просят произведение или количество ходов.

Оптимальный маршрут, маршрут с максимальной или минимальной стоимостью среди всех допустимых.

Принцип оптимальности, любой кусок оптимального маршрута сам оптимален до своей клетки. Поэтому достаточно знать лучшую стоимость входа в клетку, а не все пути, которые в неё ведут.

Динамическое заполнение, для каждой клетки считают лучшую стоимость, используя уже посчитанных соседей, из которых в эту клетку можно попасть.

Препятствие, запрещённая клетка. В неё стоимость не определена, и через неё маршруты не идут.

Старт и финиш, обычно левый верхний и правый нижний углы, но условие может задать другие клетки.

Почему нельзя жадничать локально

Выбор наибольшего числа среди соседних клеток на одном шаге не гарантирует максимум всей суммы: выгодный ход может вести в тупик с мелкими числами. Нужен учёт всей оставшейся (или всей прошедшей) стоимости через динамику.

Общий алгоритм решения

1. Зафиксировать размер таблицы, стартовую клетку, финиш и множество ходов.
2. Определить, что оптимизируют: максимум суммы, минимум, количество путей.
3. Выбрать порядок обхода клеток так, чтобы все предшественники клетки были уже вычислены.
4. Для стартовой клетки значение равно её числу (или 1, если считают пути).
5. Для каждой следующей клетки взять максимум/минимум/сумму по допустимым предшественникам и добавить число клетки, если это сумма.
6. Ответ взять из финишной клетки. Если туда нельзя попасть, маршрутов нет, это нужно отличить от нулевой суммы.