Un nombre limité de diagonales

• On ajoute un paramètre, le nombre de pas NE encore permis.

Base. $m(0,0,k)=g(0,0)$ pour tout $k$.

Hérédité. Pour $(l,c)\ne (0,0)$ et $0\le k<K+1$ :

$$m(l,c,k)=\max \{m(l-1,c,k),m(l,c-1,k),m(l-1,c-1,k-1)\}+g(l,c),$$

le dernier terme n'existant que si $k\ge 1$ (et les cases hors grille étant omises). -

for (int l = 0; l < L; l++)
    for (int c = 0; c < C; c++)
        for (int k = 0; k < K + 1; k++) {
            if (l == 0 && c == 0) { M[0][0][k] = G[0][0]; continue; }   // base
            int p = MOINS_INFINI;
            if (l > 0) p = Math.max(p, M[l - 1][c][k]);                  // pas N
            if (c > 0) p = Math.max(p, M[l][c - 1][k]);                  // pas E
            if (l > 0 && c > 0 && k > 0) p = Math.max(p, M[l - 1][c - 1][k - 1]); // pas NE
            M[l][c][k] = p + G[l][c];
        }

K = 0 : 22
K = 1 : 28
K = 2 : 28
K = 3 : 28
K = 4 : 28

Sans diagonale, le meilleur chemin vaut $22$ ; une seule diagonale suffit à retrouver la valeur $28$ du chapitre, dont le chemin optimal n'en emploie qu'une.

• $L\times C\times (K+1)$ cases en temps constant : $\Theta (LCK)$.