Zébulon change de ressort

• Le dernier saut vers $j$ part de $j-1$, $j-2$ ou $j-3$ (quand ces cases existent). Base : $m(0)=r_0$. Hérédité : $\forall j,1\le j<n$,

$$m(j)=\max \{m(j-i):i\in \{1,2,3\},j-i\ge 0\}+r_j.$$

Toutes les cases sont désormais accessibles : plus besoin de $-\infty$. -

static int[] calculerM(int[] R) { int n = R.length;
    int[] M = new int[n];
    M[0] = R[0];                                     // base
    for (int j = 1; j < n; j++) {                    // hérédité, j croissants
        int best = M[j-1];                           // arrivée depuis j-1
        if (j >= 2) best = Math.max(best, M[j-2]);   // depuis j-2
        if (j >= 3) best = Math.max(best, M[j-3]);   // depuis j-3
        M[j] = best + R[j];
    }
    return M;
}
static void acm(int[] M, int j) {
    // affiche un chemin de valeur maximum de 0 à j
    if (j == 0) { System.out.print("0"); return; }   // base
    int p = j - 1;                                   // case qui précède j
    for (int d = 2; d <= 3; d++)
        if (j - d >= 0 && M[j-d] > M[p]) p = j - d;
    acm(M, p);                                       // chemin jusqu'à p affiché
    System.out.print(" -> " + j);                   // donc chemin jusqu'à j affiché
}

-

M = [1, 6, 7, 6, -13, -23, 26]
valeur maximum 26 : 0 -> 1 -> 2 -> 3 -> 6

La valeur passe de $20$ à $26$ : la case $1$ (valeur $5$), inaccessible avec des sauts de $2$ ou $3$, peut maintenant être ramassée. Ajouter des possibilités ne peut qu'augmenter (au sens large) le maximum.

nom : R
valeurs : 1 5 1 -1 -20 -30 20
vert : 0..3 6
fleches : 0->1 1->2 2->3 3->6
legende : sauts de 1, 2 ou 3 : chemin 0 → 1 → 2 → 3 → 6, de valeur 26