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