Можно ли это классифицировать как динамическое программирование или жадное решение?

Question

Дана таблица, состоящая из клеток N x M, каждая из которых имеет определенное количество яблок. Вы начинаете с верхнего левого угла. На каждом шагу вы можете спуститься или повернуть по одной ячейке. Найдите максимальное количество яблок, которые вы можете собрать.

Answer 1

Наиболее характерный жадный подход, определенный ниже не работает для этой проблемы.

В каждой клетке, выбрать либо ячейку справа или в нижней части, которая содержит больше яблок

Рассмотрим следующий пример:

0 0 0 0 
1 0 0 5 
1 0 0 0 
1 0 0 0 

Жадный подход займет путь M[0, 0] → M[3, 0] → M[3, 3] (из верхнего левого угла в нижний левый угол, а затем в нижний правый угол), что дает нам три яблока. Это явно не оптимальное решение для этого случая.

Чтобы решить эту проблему, необходимо развернуть технологию динамического программирования. Пусть D[i, j] обозначает оптимальное решение, начиная с верхнего левого угла (0, 0) в (i, j), так как на каждом шаге мы можем либо пойти вниз или пойти направо, то, очевидно, мы имеем следующее соотношение между подзадачи:

D[i, j] = c(i, j) + max{ D[i - 1, j], D[i, j - 1] } 

где c(i, j) обозначает количество яблок в (i, j). Начиная с наименьшей подзадачи D[0, 0] = c(0, 0), мы можем использовать приведенную выше формулу для вычисления D[N, M] путем оценки значений сразу же под-проблем.