La cueillette sans voisins

La cueillette sans voisins.

Des arbres fruitiers sont plantés en ligne ; l'arbre $i$ porte v[i] kilogrammes de fruits. Pour ne pas épuiser le verger, on s'interdit de récolter deux arbres voisins. On veut maximiser la récolte.

• Sur v = [2, 7, 9, 3, 1], comparer la stratégie « tous les arbres d'indice pair » et la stratégie « tous les arbres d'indice impair ». L'une d'elles est-elle optimale ?
• On note $R_i$ la meilleure récolte possible avec les arbres $0$ à $i-1$. Justifier que $R_i=\max (R_{i-1},R_{i-2}+v[i-1])$, avec $R_0=0$ et $R_1=v[0]$.
• Écrire une fonction recolte_max(v) en $O(n)$ et l'appliquer à l'exemple et à [6, 7, 1, 30, 8, 2, 4].