Le glouton pris en défaut

• Depuis $(0,0)$ (valeur $1$), les cases accessibles valent $2$ (N), $5$ (E) et $-10$ (NE) : le glouton va à l'Est. Depuis $(0,1)$ : N vaut $-10$, E et NE valent $0$ ; il va à l'Est, puis monte deux fois. Chemin $(0,0)\to (0,1)\to (0,2)\to (1,2)\to (2,2)$, de valeur $1+5+0+0+1=7$. -

glouton : (0,0)->(0,1)->(0,2)->(1,2)->(2,2), somme 7
M ligne 2 : [12, 13, 14]
M ligne 1 : [3, -4, 6]
M ligne 0 : [1, 6, 6]
optimum : 14

Le chemin optimal $(0,0)\to (1,0)\to (2,0)\to (2,1)\to (2,2)$ vaut $1+2+9+1+1=14$.

• Le glouton préfère le $5$ immédiat au $2$, sans voir que le $2$ ouvre l'accès au $9$. Une décision localement bonne ferme une possibilité globalement meilleure : c'est exactement ce que la récurrence évite, en comparant tous les chemins par l'intermédiaire de leurs valeurs $m(l,c)$.