Решение: Максимум и минимум монет
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Исполнитель Робот может перемещаться только вправо или вниз, если между соседними клетками нет стены. Посетив клетку, Робот забирает находящуюся в ней монету, включая начальную и конечную клетки маршрута. Определите максимальную и минимальную денежные суммы, которые может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. Исходные данные представлены в прилагаемом файле — электронной таблице размером $N \times N$; внутренние и внешние стены обозначены утолщёнными линиями.
Решение по шагам
4 шагаОбозначим через $F_{\max}(i,j)$ максимальную сумму, которую можно собрать при попадании в клетку $(i,j)$, а через $F_{\min}(i,j)$ — минимальную сумму.
Для каждой клетки учитываем только те переходы сверху или слева, которые не пересекают стену.
Если $a_{ij}$ — достоинство монеты в клетке, то для допустимых переходов используем рекуррентные формулы:
$$F_{\max}(i,j)=a_{ij}+\max F_{\max}(\text{допустимые предшественники});\quad F_{\min}(i,j)=a_{ij}+\min F_{\min}(\text{допустимые предшественники})$$Начальная клетка получает значение своей монеты. После заполнения таблиц считываем значения в правой нижней клетке.
Точные значения максимальной и минимальной сумм невозможно определить без содержимого прилагаемой электронной таблицы.
Этот ответ получен в разборе, но не сверен с официальным ключом из банка — проверьте выкладки, прежде чем заучивать результат.
Где здесь ошибаются
Не учитывать монету в начальной или конечной клетке.
Разрешать переход через внутреннюю стену.
Использовать минимум для максимальной суммы или максимум для минимальной.
Учитывать только один из возможных переходов, не проверяя наличие стены.