Как решить эту задачу динамическое программирование?

Question

[DJjopa]

Прямоугольный остров разделён на квадраты так, что его размеры — N х М квадратов. В каждом квадрате зарыто некоторое число золотых монет, эти данные хранятся в матрице (двумерном массиве) Z, где Z[i, j] — число монет в квадрате с координатами (i, j). Пират хочет пройти из юго-западного угла острова в северо-восточный, причём он может двигаться только на север или на восток. Как пирату собрать наибольшее количество монет? Напишите программу, которая находит оптимальный путь пирата и число монет, которое ему удастся собрать.

Comments

[Sand]

Очень похоже на задачу коммивояжора

[Wataru]

Sand, Это же самая стандартная задача на ДП.

Answer 1

[Wataru]

Это стандартное упражнение на ДП.

F(i,j) - максимальное количество монет, которые можно собрать придя в точку (i, j).

F(0,0) = Z[0,0]
F(i,j) = Z[i,j] + max(F(i-1,j), F(i,j-1))
F(-1,*) = F(*,-1) = -100500
ответ - F(n,m)

Для восстановления пути сохраняйте в каждой ячейке, с какой стороны взят максимум - сверху или слева. И разворачивайте ответ с конца по этим ссылкам.

Comments

[DJjopa]

Спасибо огромное : )