[Algorytmy] Zbieranie monet po drodze

[calmosc]

Cześć, chciałbym rozwiązać następujący problem:
mamy prostokątną planszę o wysokości h i szerokości w, składa się z w*h pól, na niektórych polach są monety, startujemy z lewego górnego rogu i kończymy na prawym dolnym. Można poruszać się tylko w prawo i na dół. Algorytm ma wyznaczyć maksymalną liczbę monet, które można zebrać po drodze na podstawie podanej planszy.
Podobno należy użyć programowania dynamicznego, ale jestem nowicjuszem i od dłuższego czasu już nie mogę na nic wpaść - co prawda znalazłem jakieś algorytmy zachłanne, ale nie są poprawne, bo istnieją odpowiednie kontrprzykłady.
Czy mógłbym prosić o jakieś wskazówki pomocne w pokonaniu tego zadania? Z góry dziękuję.

[Afish]

W każdym polu możesz zdobyć liczbę monet będącą maksimum z pola powyżej oraz z pola z lewej strony, plus ewentualna moneta na tym polu. Iterujesz po planszy od górnego lewego rogu do dolnego prawego po wierszach i aktualizujesz wartości. Potrzebujesz pamiętać tylko dwa wiersze (aktualnie analizowany i jeden wyżej).

[Andreas]

Idziesz od drugiej strony planszy (czyli od prawego dolnego rogu) i dla każdego pola sprawdzasz wartość monet na dół i na prawo od niego. Bierzesz większą z nich i dodajesz do wartości badanego pola. Liczba którą będziesz miał w lewym górnym rogu będzie twoim rozwiązaniem.

[calmosc]

Rzeczywiście, że też na to nie wpadłem. Już myślałem o jakimś iterowaniu po diagonalach, a to jednak wcale nie ma przerażającego rozwiązania. Implementacja w C++ zakończona, wszystko działa, wybrałem sposób Afish'a, bo na dobrą sprawę czy idzie się od końca, czy od początku, to jest to bez różnicy, bo można planszę obrócić i ma się zamienione rogi. Bardzo dziękuję za pomoc i przy następnym problemie nie będę się wahał gdzie napisać.