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