Au plus $Q$ grands sauts

• Un chemin optimal jusqu'à $j$ peut avoir épuisé les grands sauts dont un prolongement aurait besoin : la valeur doit retenir combien il en reste. Soit $m(j,q)$ la valeur maximum d'un chemin de $0$ à $j$ utilisant au plus $q$ sauts de $3$. Base : $m(0,q)=r_0$ pour tout $q$. Hérédité : $\forall j\ge 1$, $\forall q,0\le q<Q+1$,

$$m(j,q)=\max \{m(j-2,q),m(j-3,q-1)\}+r_j,$$

où un terme est remplacé par $-\infty$ lorsque $j-2<0$, $j-3<0$ ou $q=0$.

• $m(j,q)$ dépend de valeurs de $j$ strictement plus petit : on calcule par $j$ croissants (pour chaque $q$, ou $q$ par $q$). Il y a $n(Q+1)$ valeurs, chacune en temps constant : $\Theta (nQ)$.

static int[][] calculerM(int[] R, int Q) { int n = R.length;
    int[][] M = new int[n][Q + 1];
    for (int q = 0; q < Q + 1; q++) {
        M[0][q] = R[0];                                           // base
        for (int j = 1; j < n; j++) {
            int best = MOINS_INFINI;
            if (j >= 2) best = Math.max(best, M[j-2][q]);             // saut de 2
            if (j >= 3 && q >= 1) best = Math.max(best, M[j-3][q-1]); // saut de 3
            M[j][q] = (best <= MOINS_INFINI / 2) ? MOINS_INFINI : best + R[j];
        }
    }
    return M;
}

• Le programme donne $m(6,0)=2$, $m(6,1)=2$, $m(6,2)=20$. Pour aller de $0$ à $6$, la somme des sauts vaut $6$ : soit trois sauts de $2$, soit deux sauts de $3$. Avec un seul grand saut autorisé, le chemin $0\to 3\to 6$ est interdit, et il ne reste que $0\to 2\to 4\to 6$.