L'approche ascendante : remplir un tableau

Il existe une seconde façon d'appliquer la programmation dynamique, sans aucune récursion : l'approche ascendante (« bottom-up »). Au lieu de partir du grand problème et de redescendre vers les petits cas (comme la mémoïsation), on part des plus petits cas et on remonte en remplissant un tableau dp, case après case.

Prenons un exemple classique : compter le nombre de façons de monter un escalier de n marches, sachant qu'à chaque pas on avance de 1 ou de 2 marches. Notons dp[i] ce nombre de façons pour i marches. Pour atteindre la marche i, on vient forcément soit de la marche i-1 (en montant 1 marche), soit de la marche i-2 (en montant 2 marches). Donc dp[i] = dp[i-1] + dp[i-2] — on retrouve exactement la récurrence de Fibonacci, mais posée sur un vrai problème concret.

On initialise dp[0]=1 (une seule façon de rester sur place : ne rien faire) et dp[1]=1 (une seule façon d'atteindre la marche 1 : un pas de 1). Regarde le tableau se remplir étape par étape pour n=6 :

dp[0] = 1                          (base : 0 marche, 1 facon = ne rien faire)
dp[1] = 1                          (base : 1 marche, 1 facon = pas de 1)
dp[2] = dp[1] + dp[0] = 1 + 1 = 2
dp[3] = dp[2] + dp[1] = 2 + 1 = 3
dp[4] = dp[3] + dp[2] = 3 + 2 = 5
dp[5] = dp[4] + dp[3] = 5 + 3 = 8
dp[6] = dp[5] + dp[4] = 8 + 5 = 13

tableau final : [1, 1, 2, 3, 5, 8, 13]
                  0  1  2  3  4  5  6   (indice = nombre de marches)

Chaque case ne dépend que des deux cases précédentes déjà remplies : il n'y a jamais besoin de recalculer quoi que ce soit, puisqu'on avance toujours vers l'avant. C'est l'esprit même de la programmation dynamique ascendante : construire la solution du bas vers le haut, en réutilisant systématiquement ce qui a déjà été posé dans le tableau.