Une seule ligne de mémoire

• L'hérédité n'emploie que des valeurs $m(k-1,\cdot )$ : la ligne $M[k]$ se calcule à partir de la seule ligne $M[k-1]$.
• La case $m(k,s)$ dépend des cases $m(k-1,s-s^{\prime })$, toutes situées dans les colonnes $0$ à $s$. Si l'on parcourt les $s$ par valeurs décroissantes dans un tableau unique $L$, les cases $L[0],\dots ,L[s]$ contiennent encore la ligne $k-1$ au moment où l'on calcule $m(k,s)$.

nom : L
valeurs : 0 4 6 7 9 10
colorier : 3
vert : 4 5
zone : 0..3 ligne 3
zone : 4..5 ligne 4
legende : tour k = 4, s = 3 : L[0:4] = M[3][0:4] et L[4:6] = M[4][4:6]

static int calculerMn(int[][] G) {
    int n = G.length, S = G[0].length - 1;
    int[] L = new int[S + 1];                 // L = M[0] : que des zéros
    for (int k = 1; k < n + 1; k++)
        // invariant : L[0:s+1] contient M[k-1][0:s+1] et L[s+1:S+1] contient M[k][s+1:S+1]
        for (int s = S; s >= 0; s--) {        // par s DÉCROISSANTS
            int best = Integer.MIN_VALUE;
            for (int sp = 0; sp < s + 1; sp++)
                best = Math.max(best, G[k - 1][sp] + L[s - sp]); // L[s-sp] = M[k-1][s-sp]
            L[s] = best;                       // L[s] = M[k][s]
        }
    return L[S];
}

Sur l'exemple du chapitre, le programme retourne bien $m(4,5)=10$. La mémoire passe de $\Theta (nS)$ à $\Theta (S)$ ; le temps reste $\Theta (n{S}^2)$.

• La reconstruction a besoin des arguments $a(k,s)$ pour toutes les lignes $k$, de $n$ à $1$ : ils ne sont plus disponibles. Il faudrait garder le tableau $A$, ce qui ramène la mémoire à $\Theta (nS)$.