Glouton ou dynamique ?

1.1 Un premier problème : Zébulon sur son ruban

Un ruban $R$ est divisé en $n$ cases numérotées $0,\dots ,n-1$ ; la case $i$ porte une valeur entière $r_i$, positive ou négative. Zébulon, petit personnage monté sur ressort, se trouve sur la case $0$. Depuis la case $i$, il peut sauter sur la case $i+2$ ou sur la case $i+3$ (jamais en arrière, jamais d'une seule case). Un chemin est la suite des cases sur lesquelles il se pose ; sa valeur est la somme des valeurs de ces cases.

Exemple 1.1un ruban de 7 cases

Ici $R=[1,5,1,-1,-20,-30,20]$. On remarque que la case $1$ est inaccessible : sa valeur $5$ ne pourra jamais être ramassée.

1.1.1 La tentation gloutonne

L'idée la plus naturelle est de faire, à chaque saut, le meilleur choix immédiat : sauter sur celle des deux cases accessibles qui a la plus grande valeur.

Sur notre ruban, depuis la case $0$ le glouton choisit la case $2$ (valeur $1$) plutôt que la case $3$ (valeur $-1$) ; puis la case $4$ ($-20$) plutôt que la case $5$ ($-30$) ; puis la case $6$. Le chemin glouton $0\to 2\to 4\to 6$ a pour valeur $1+1-20+20=2$.

Or le chemin $0\to 3\to 6$ vaut $1-1+20=20$. En acceptant une petite perte au premier saut, on évite la case $-20$. La stratégie gloutonne ne résout pas le problème posé.