Исполнитель Робот стоит в правом нижнем углу прямоугольного поля, в каждой клетке которого записано натуральное число.

Question

Вопрос:

Исполнитель Робот стоит в правом нижнем углу прямоугольного поля, в каждой клетке которого записано натуральное число.

Фотография

Ответ ассистента

Accepted Answer

Для решения задачи воспользуемся методом динамического программирования. Робот начинает движение из левой верхней клетки (в условии опечатка, но по смыслу классических задач такого типа он идет из одной противоположной стороны в другую) и заканчивает в правой нижней. Пусть $S[i][j]$ — максимальная (или минимальная) сумма, которую можно собрать в клетке $(i, j)$. Значение в клетке $(i, j)$ складывается из значения самой клетки и лучшего (макс/мин) результата из клетки сверху или слева. ### Поиск минимальной суммы | | | | | |---|---|---|---| | 20 | 32 | 43 | 64 | | 38 | 52 | 48 | 68 | | 44 | 62 | 58 | 73 | | 51 | 60 | 65 | 101 | Минимальная сумма: 101. ### Поиск максимальной суммы | | | | | |---|---|---|---| | 20 | 32 | 43 | 64 | | 38 | 58 | 63 | 84 | | 44 | 76 | 86 | 101 | | 51 | 85 | 93 | 137 | Максимальная сумма: 137. Ответ: 101 137

Исполнитель Робот стоит в правом нижнем углу прямоугольного поля, в каждой клетке которого записано натуральное число.

Ответ ассистента

Другие решения