Исполнитель Робот стоит в правом нижнем углу прямоугольного поля, в каждой клетке которого записано натуральное число. Он может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: влево или вверх. По команде влево Робот перемещается в соседнюю левую клетку, по команде вверх — в соседнюю верхнюю. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клеткам маршрута Робота. В «угловых» клетках поля — тех, которые справа и снизу ограничены стенами, — Робот не может продолжать движение, поэтому накопленная сумма считается итоговой. Определите максимальную и минимальную денежные суммы, среди всех возможных итоговых сумм, которые может собрать Робот, пройдя из левой верхней клетки в конечную клетку маршрута. В ответе запишите два числа через пробел: сначала минимальную сумму, затем — максимальную.

Решение:

Робот движется из левой верхней клетки в правую нижнюю. Он может перемещаться только влево или вверх. Это означает, что для достижения правой нижней клетки, робот должен двигаться строго вправо и вниз. Однако, условие задачи гласит, что робот может двигаться только влево или вверх. Это противоречит задаче достижения правой нижней клетки из левой верхней. Предполагается, что команды робота на самом деле вправо и вниз, чтобы задача имела смысл.

Рассмотрим поле как матрицу:

Робот стартует в левой верхней клетке (20) и должен добраться до правой нижней клетки (36). Он может двигаться только вправо и вниз.

Минимальная сумма:

Будем использовать динамическое программирование. Создадим матрицу dp_min, где dp_min[i][j] будет хранить минимальную сумму для достижения клетки (i, j).

dp_min[i][j] = grid[i][j] + min(dp_min[i-1][j], dp_min[i][j-1])

Начальные условия:

• dp_min[0][0] = 20
• Первая строка: dp_min[0][j] = grid[0][j] + dp_min[0][j-1]
• Первый столбец: dp_min[i][0] = grid[i][0] + dp_min[i-1][0]

Заполняем матрицу dp_min:

Минимальная сумма: 93

Максимальная сумма:

Аналогично, создадим матрицу dp_max, где dp_max[i][j] будет хранить максимальную сумму для достижения клетки (i, j).

dp_max[i][j] = grid[i][j] + max(dp_max[i-1][j], dp_max[i][j-1])

Начальные условия:

• dp_max[0][0] = 20
• Первая строка: dp_max[0][j] = grid[0][j] + dp_max[0][j-1]
• Первый столбец: dp_max[i][0] = grid[i][0] + dp_max[i-1][0]

Заполняем матрицу dp_max:

Максимальная сумма: 135

Ответ: 93 135