La mémoïsation et les sous-problèmes qui se chevauchent

La programmation dynamique repose sur une idée simple : quand un problème se découpe en sous-problèmes qui SE RÉPÈTENT (on dit qu'ils se chevauchent), il suffit de calculer chaque sous-problème une seule fois et de mémoriser (stocker) son résultat dans un dictionnaire ou un tableau. La prochaine fois qu'on en a besoin, on le relit directement au lieu de le recalculer. Cette technique s'appelle la mémoïsation.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

Avec cette version, chaque valeur fib(k) n'est calculée qu'une seule fois, puis stockée dans memo. L'arbre d'appels ne « ré-explose » plus : dès qu'un sous-problème déjà vu réapparaît, on le lit en mémoire au lieu de redescendre dans les branches.

fib_memo(5) : arbre reel des CALCULS (pas des simples lectures)

fib(5)
  fib(4)
    fib(3)
      fib(2)
        fib(1)   (calcule)
        fib(0)   (calcule)
      fib(1)      (lu en memoire, pas recalcule)
    fib(2)        (lu en memoire, pas recalcule)
  fib(3)          (lu en memoire, pas recalcule)

seulement 6 calculs reels (fib(0) a fib(5)), le reste est lu en O(1)

Ce principe des « sous-problèmes qui se chevauchent » est la condition centrale pour appliquer la programmation dynamique : si les sous-problèmes ne se répètent jamais, mémoriser ne sert à rien (c'est le cas par exemple du tri fusion, où chaque sous-tableau est différent). Avec la mémoïsation, on passe d'une complexité exponentielle à une complexité linéaire O(n) pour Fibonacci : chaque valeur de 0 à n est calculée exactement une fois.