@DJjopa

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

Прямоугольный остров разделён на квадраты так, что его размеры — N х М квадратов. В каждом квадрате зарыто некоторое число золотых монет, эти данные хранятся в матрице (двумерном массиве) Z, где Z[i, j] — число монет в квадрате с координатами (i, j). Пират хочет пройти из юго-западного угла острова в северо-восточный, причём он может двигаться только на север или на восток. Как пирату собрать наибольшее количество монет? Напишите программу, которая находит оптимальный путь пирата и число монет, которое ему удастся собрать.
  • Вопрос задан
  • 230 просмотров
Пригласить эксперта
Ответы на вопрос 1
wataru
@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)

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы