Sia data una tabella come in figura
L’obiettivo è, partendo da una casella della prima riga (R1), arrivare a una dell’ottava riga (R8), minimizzando la somma dei valori nelle caselle dalle quali si passa.
Le mosse consentite sono: un passo verso l’alto in verticale, un passo verso l’alto a sinistra, un passo verso l’alto a destra (per esempio, dalla casella (R2,C3) si può andare in (R3,C3), (R3,C2) oppure (R3,C4)).
Quanto vale la somma minima S di un percorso dalla prima all’ultima riga?
Risposta: S=26
A partire dalla riga R2 in poi sostituisci il contenuto di ogni cella con la somma del suo valore e del minimo tra i 3 (o 2) valori contenuti nelle celle adiacenti della riga precedente.
