Le code de la montée d'escalier

Traduisons le remplissage du tableau vu précédemment en code Python. On crée un tableau dp de taille n+1, on fixe les deux valeurs de base, puis on remplit chaque case avec une simple boucle, sans aucune récursion ni appel redondant.

def escalier(n):
    if n == 0:
        return 1
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

Cette version bottom-up a une complexité en temps O(n) : une seule boucle qui remplit n+1 cases, chacune en temps constant. C'est le même ordre de grandeur que la version mémoïsée, mais sans le risque de dépassement de la pile d'appels (« stack overflow ») qui peut survenir avec une récursion trop profonde, et sans le coût caché des appels de fonction récursifs.

On peut même réduire la mémoire utilisée : puisque dp[i] ne dépend que des deux cases précédentes, il n'est pas nécessaire de garder tout le tableau, seulement les deux dernières valeurs :

def escalier_optimise(n):
    if n == 0:
        return 1
    precedent, courant = 1, 1   (dp[0], dp[1])
    for i in range(2, n + 1):
        precedent, courant = courant, precedent + courant
    return courant

Cette même méthode s'applique à d'autres problèmes classiques comme le rendu de monnaie (compter le nombre minimal de pièces pour atteindre une somme) : on construit un tableau dp où dp[s] représente le coût minimal pour la somme s, en le déduisant des valeurs dp[s - piece] déjà calculées pour chaque pièce disponible. Le principe reste identique : identifier la récurrence entre sous-problèmes, puis remplir un tableau du plus petit cas vers le plus grand, sans jamais recalculer une case déjà posée.