Méthodes de la programmation dynamique : Mémoisation et tabulation

Mémoisation et tabulation : deux approches de programmation dynamique

Mémoisation et tabulation sont deux approches couramment utilisées pour optimiser les solutions de programmation dynamique. Elles permettent de résoudre les problèmes plus efficacement en stockant les résultats intermédiaires pour éviter les calculs répétitifs.

La mémoisation (approche top-down)

Exemple classique : La suite de Fibonacci avec mémoisation

Le problème de la suite de Fibonacci est un exemple parfait pour illustrer la mémoisation. Lors de l'utilisation de la récursion simple, le même calcul est effectué plusieurs fois pour des valeurs répétées.

Version récursive simple (sans optimisation)

def fibonacci_simple(n):
    """Version récursive naïve - très inefficace pour n > 30"""
    if n < 2:
        return n  # F(0)=0, F(1)=1
    return fibonacci_simple(n-1) + fibonacci_simple(n-2)

# Problème : de nombreux calculs redondants !
# Pour n=5, F(3) est calculé deux fois, F(2) trois fois, etc.

Version avec mémoisation

def fibonacci_memo(n, cache=None):
    """
    Calcule le n-ième nombre de Fibonacci avec mémoisation
    
    Paramètres:
        n (int): Indice du nombre de Fibonacci à calculer
        cache (dict): Dictionnaire pour stocker les résultats intermédiaires
        
    Retourne:
        int: La valeur de F(n)
    """
    # Initialisation du cache si nécessaire
    if cache is None:
        cache = {}
    
    # Condition de base
    if n < 2:
        return n  # F(0)=0, F(1)=1
    
    # Vérification du cache
    if n not in cache:
        # Calcul récursif avec stockage du résultat
        cache[n] = fibonacci_memo(n-1, cache) + fibonacci_memo(n-2, cache)
    
    # Retour de la valeur en cache
    return cache[n]

# Test
print(fibonacci_memo(10))   # 55
print(fibonacci_memo(100))  # 354224848179261915075 (instantané)

Version avec décorateur @lru_cache (Pythonique)

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    """Version avec décorateur de mémoisation intégré"""
    if n < 2:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(100))  # 354224848179261915075
print(fibonacci.cache_info())  # CacheInfo(hits=98, misses=101, maxsize=None, currsize=101)

La tabulation (approche bottom-up)

Exemple : Fibonacci avec tabulation

def fibonacci_tabu(n):
    """
    Calcule le n-ième nombre de Fibonacci avec tabulation (bottom-up)
    
    Paramètres:
        n (int): Indice du nombre de Fibonacci à calculer
        
    Retourne:
        int: La valeur de F(n)
    """
    if n < 2:
        return n
    
    # Création du tableau pour stocker tous les résultats
    tab = [0] * (n + 1)
    tab[0] = 0
    tab[1] = 1
    
    # Remplissage itératif du tableau
    for i in range(2, n + 1):
        tab[i] = tab[i-1] + tab[i-2]
    
    return tab[n]

# Version optimisée en mémoire (sans tableau complet)
def fibonacci_tabu_optime(n):
    """Version avec seulement deux variables (O(1) mémoire)"""
    if n < 2:
        return n
    
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    
    return b

print(fibonacci_tabu(100))        # 354224848179261915075
print(fibonacci_tabu_optime(100)) # 354224848179261915075

Comparaison : Mémoisation vs Tabulation

Étude de cas : Problème du nombre minimum de sauts

Exemple : tab = [2, 3, 1, 1, 2, 4, 2, 9, 1, 1, 1, 3, 5]

Ce problème illustre parfaitement la différence entre les deux approches, car tous les sous-problèmes ne sont pas nécessairement utiles pour trouver la solution optimale.

Solution 1 : Mémoisation (approche descendante)

def min_sauts_memo(tab, index=0, memo=None):
    """
    Calcule le nombre minimum de sauts pour atteindre la fin du tableau
    Version avec mémoisation (top-down)
    
    Paramètres:
        tab (list): Tableau des longueurs de sauts
        index (int): Position actuelle
        memo (dict): Cache des résultats déjà calculés
        
    Retourne:
        int: Nombre minimum de sauts, ou infini si impossible
    """
    if memo is None:
        memo = {}
    
    # Cas de base : on est déjà à la fin
    if index == len(tab) - 1:
        return 0
    
    # Cas de base : on dépasse la fin (solution invalide)
    if index >= len(tab):
        return float('inf')
    
    # Vérification du cache
    if index in memo:
        return memo[index]
    
    # Nombre maximum de pas qu'on peut faire depuis cette position
    max_saut = tab[index]
    
    # Si on ne peut pas avancer (valeur 0) et qu'on n'est pas à la fin
    if max_saut == 0 and index < len(tab) - 1:
        memo[index] = float('inf')
        return float('inf')
    
    # Exploration de toutes les possibilités de saut
    min_sauts = float('inf')
    
    for i in range(1, max_saut + 1):
        sauts = min_sauts_memo(tab, index + i, memo)
        min_sauts = min(min_sauts, sauts + 1)
    
    # Stockage du résultat dans le cache
    memo[index] = min_sauts
    return min_sauts


# Test
tab = [2, 3, 1, 1, 2, 4, 2, 9, 1, 1, 1, 3, 5]
resultat = min_sauts_memo(tab)
print(f"Nombre minimum de sauts (mémoisation) : {resultat}")

# Affichage du cache pour voir quels indices ont été calculés
print("Indices calculés :", sorted(memo.keys()))

Solution 2 : Tabulation (approche ascendante)

def min_sauts_tabu(tab):
    """
    Calcule le nombre minimum de sauts pour atteindre la fin du tableau
    Version avec tabulation (bottom-up)
    
    Paramètres:
        tab (list): Tableau des longueurs de sauts
        
    Retourne:
        int: Nombre minimum de sauts, ou -1 si impossible
    """
    n = len(tab)
    
    # Tableau pour stocker le nombre minimum de sauts pour atteindre chaque position
    # Initialisé à l'infini
    sauts = [float('inf')] * n
    sauts[0] = 0  # 0 saut pour atteindre la première position
    
    # Parcours de toutes les positions
    for i in range(1, n):
        # Pour chaque position i, on regarde toutes les positions précédentes j
        for j in range(i):
            # Si on peut atteindre i depuis j (j + tab[j] >= i)
            if j + tab[j] >= i:
                sauts[i] = min(sauts[i], sauts[j] + 1)
    
    print("Tableau des sauts minimum par position:", sauts)
    
    # Retourne le nombre de sauts pour atteindre la dernière position
    return sauts[-1] if sauts[-1] != float('inf') else -1


# Test
tab = [2, 3, 1, 1, 2, 4, 2, 9, 1, 1, 1, 3, 5]
resultat = min_sauts_tabu(tab)
print(f"Nombre minimum de sauts (tabulation) : {resultat}")

Comparaison des deux approches sur ce problème

Autre exemple : Le problème du sac à dos (Knapsack)

La tabulation est particulièrement efficace pour ce problème :

def knapsack_tabu(poids, valeurs, capacite):
    """
    Résout le problème du sac à dos par tabulation
    
    Paramètres:
        poids (list): Poids des objets
        valeurs (list): Valeurs des objets
        capacite (int): Capacité maximale du sac
        
    Retourne:
        int: Valeur maximale atteignable
    """
    n = len(poids)
    
    # Création d'une matrice (n+1) x (capacite+1)
    dp = [[0] * (capacite + 1) for _ in range(n + 1)]
    
    # Remplissage de la matrice
    for i in range(1, n + 1):
        for w in range(1, capacite + 1):
            if poids[i-1] <= w:
                # On peut prendre l'objet i-1
                dp[i][w] = max(
                    valeurs[i-1] + dp[i-1][w - poids[i-1]],  # On le prend
                    dp[i-1][w]  # On ne le prend pas
                )
            else:
                # L'objet est trop lourd
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacite]

# Exemple
poids = [2, 3, 4, 5]
valeurs = [3, 4, 5, 6]
capacite = 5
print(f"Valeur maximale: {knapsack_tabu(poids, valeurs, capacite)}")  # 7

from functools import lru_cache

# Version 1 : Mémoisation (top-down)
@lru_cache(maxsize=None)
def chemins_memo(m, n):
    """Nombre de chemins uniques de (0,0) à (m,n)"""
    # Cas de base : une seule ligne ou une seule colonne
    if m == 0 or n == 0:
        return 1
    
    # Relation de récurrence : chemins(m,n) = chemins(m-1,n) + chemins(m,n-1)
    return chemins_memo(m-1, n) + chemins_memo(m, n-1)

# Version 2 : Tabulation (bottom-up)
def chemins_tabu(m, n):
    """Nombre de chemins uniques de (0,0) à (m,n) - version itérative"""
    # Création d'une matrice (m+1) x (n+1)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initialisation : première ligne et première colonne = 1
    for i in range(m + 1):
        dp[i][0] = 1
    for j in range(n + 1):
        dp[0][j] = 1
    
    # Remplissage de la matrice
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    return dp[m][n]

# Version optimisée en mémoire (une seule ligne)
def chemins_tabu_optime(m, n):
    """Version avec seulement O(n) mémoire"""
    # On ne garde qu'une ligne
    ligne = [1] * (n + 1)
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            ligne[j] += ligne[j-1]
    
    return ligne[n]

# Tests
m, n = 10, 10
print(f"Mémoisation : {chemins_memo(m, n)}")
print(f"Tabulation : {chemins_tabu(m, n)}")
print(f"Tabulation optimisée : {chemins_tabu_optime(m, n)}")