Programmation dynamique — Mémoïsation

La mémoïsation est une technique d'optimisation qui consiste à stocker les résultats intermédiaires d'une fonction pour éviter de les recalculer. Elle est particulièrement utile pour résoudre des problèmes récursifs avec des sous-problèmes redondants, comme dans la suite de Fibonacci ou le calcul des combinaisons.

Principe de base

1. Définition : La mémoïsation transforme une fonction récursive en une fonction itérative avec cache.
2. Structure : On utilise un dictionnaire (ou tableau) pour mémoriser les résultats déjà calculés.
3. Condition : Avant de calculer une valeur, on vérifie si elle est déjà dans le cache.

Exemple : Suite de Fibonacci

# Version naïve (exponentielle)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

# Version mémoïsée (linéaire)
def fib_memo(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_memo(n-1, cache) + fib_memo(n-2, cache)
    return cache[n]

Avantages et limites

• Gain de temps : Passe d'une complexité exponentielle (O(2ⁿ)) à linéaire (O(n)).
• Mémoire : Consomme de l'espace pour stocker les résultats (O(n)).
• Cas d'usage : Idéal pour les problèmes avec recouvrement de sous-problèmes (ex : calcul de combinaisons, plus court chemin).

Implémentation en Python

On peut utiliser le décorateur @functools.lru_cache pour automatiser la mémoïsation :

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_lru(n):
    if n <= 1:
        return n
    return fib_lru(n-1) + fib_lru(n-2)

Pièges à éviter

• Cache partagé : En Python, un dictionnaire comme argument par défaut peut causer des bugs (utiliser None par défaut).
• Taille du cache : Pour les très grands n, limiter la taille du cache avec maxsize.
• Problèmes sans recouvrement : La mémoïsation n'est pas utile si chaque sous-problème est unique.