Двумерное ДП

Двумерная динамика: черепашка Теперь рассмотрим такую задачу:

На каждой клетке двумерной таблички написано, сколько там лежит монет. Черепашка стоит в клетке $1 \times 1$ (верхней левой), и может двигаться только на одну клетку вниз, или на одну клетку вправо. Нужно найти максимальное число монет, которое может набрать черепашка по пути к нижней правой клетке $N \times M$.

Первое, что приходит в голову - это просто идти черепашкой в ту клетку из соседних, где лежит больше монет. К сожалению, эта жадная стратегия не всегда работает. Например, на такой доске жадная черепашка пошла бы по следу из единичек, хотя гораздо выгоднее пойти сначала по нулям, а потом найти там большие горстки монет (40, 70, 100):

1 COINS = [
2     [0,   1,   1,   1,   1,   1],
3     [0,   0,   0,   0,   0,   1],
4     [0,   40,  70,  0,   0,   1],
5     [100, 0,   0,   0,   0,   1]
6 ]