#Programmation dynamiqueCopier le lien

Prérequis : récursivité ; notation O ; notions de graphe orienté (utile pour voir la table comme un graphe de dépendances).

Objectifs d'apprentissage : reconnaître sous-structures optimales et chevauchements ; choisir entre mémoïsation et tabulation selon la forme de l'espace d'états ; réduire l'espace mémoire (tableaux glissants) ; reconstruire une solution et pas seulement sa valeur ; analyser temps et mémoire.

#Animation : de la récurrence à l'implémentationCopier le lien

#1. Les deux ingrédientsCopier le lien

• Sous-structure optimale : la solution optimale d'un problème se compose de solutions optimales de sous-problèmes (le plus court chemin de A à C via B emprunte un plus court chemin de A à B).
• Chevauchement de sous-problèmes : le même sous-problème revient plusieurs fois. Sans chevauchement, un simple diviser-pour-régner suffit et la DP n'apporte rien.

Le contre-exemple pédagogique est Fibonacci : la récursion naïve recalcule fib(n-2) une fois par appel à fib(n-1), d'où un temps exponentiel ; avec cache, chaque valeur se calcule une fois, en O(n). À l'inverse, le tri fusion ne chevauche pas ses sous-problèmes : c'est du diviser-pour-régner, pas de la DP.

#2. Mémoïsation ou tabulationCopier le lien

• Mémoïsation : descendante. On part du problème, la récursion descend vers les cas de base, chaque résultat se met en cache. Naturelle à écrire, ne visite que les états réellement utiles (précieux quand l'espace d'états est grand mais clairsemé).
• Tabulation : ascendante. On remplit une table depuis les cas de base, dans un ordre tel que chaque case ne dépend que de cases déjà remplies. Pas de risque de débordement de pile, ordre d'itération explicite, réduction d'espace facile.

Règle pratique : prototype par mémoïsation pour valider la récurrence, puis tabulation pour la version finale quand l'espace mémoire compte.

#3. Mémoïsation : FibonacciCopier le lien

Chaque état se calcule une fois : O(n) temps, O(n) pour le cache et la pile d'appels.

#4. Tabulation : Fibonacci et tableau glissantCopier le lien

1def fib_tabulation(n):2    if n < 2:3        return n4    precedent, courant = 0, 15    for _ in range(2, n + 1):6        precedent, courant = courant, precedent + courant7    return courant8 9print([fib_tabulation(i) for i in range(12)])

La table entière ne sert que les deux dernières valeurs : on la remplace par deux variables, soit O(1) mémoire. C'est la réduction d'espace standard quand la récurrence ne regarde qu'une « bande » fixe de la table.

#5. Rendu de monnaie : quand le glouton échoueCopier le lien

Problème : nombre minimal de pièces pour rendre une somme. Avec le système européen, le glouton est optimal ; avec des pièces 4 et un montant de 6, le glouton rend 4+1+1 (trois pièces) alors que 3+3 est meilleur. La DP traite tous les systèmes :

1def rendu_monnaie(pieces, montant):2    """pieces : dénomination disponibles ; montant : somme à rendre.3    Renvoie le nombre minimal de pièces, ou -1 si impossible."""4    INF = float('inf')5    dp = [0] + [INF] * montant          # dp[x] = meilleur rendu pour x6    for piece in pieces:7        for x in range(piece, montant + 1):8            dp[x] = min(dp[x], dp[x - piece] + 1)9    return dp[montant] if dp[montant] != INF else -110 11print(rendu_monnaie([1, 3, 4], 6))   # 2 -> (3, 3)12print(rendu_monnaie([3, 5], 7))      # -1 : aucune combinaison

Récurrence : dp[x] = 1 + min(dp[x - p]) sur toutes les pièces p inférieures ou égales à x, avec dp[0] = 0. Complexité : O(montant × nombre de pièces) en temps, O(montant) en mémoire. Ajoutez un tableau choix[x] mémorisant la pièce retenue pour reconstruire la liste des pièces rendues.

#6. Sac à dos 0/1 : tabulation et reconstructionCopier le lien

Chaque objet est pris une fois au plus ; on maximise la valeur sous contrainte de poids. L'étatest le couple (objets consideres, capacité restante) :

1def sac_a_dos(valeurs, poids, capacite):2    """Renvoie (meilleure valeur, liste des indices retenus)."""3    n = len(valeurs)4    dp = [[0] * (capacite + 1) for _ in range(n + 1)]5    for i in range(1, n + 1):6        for c in range(capacite + 1):7            dp[i][c] = dp[i - 1][c]                       # ne pas prendre l'objet i8            if poids[i - 1] <= c:9                dp[i][c] = max(dp[i][c],10                               dp[i - 1][c - poids[i - 1]] + valeurs[i - 1])11    # Reconstruction : remonter la table12    retenus, c = [], capacite13    for i in range(n, 0, -1):14        if dp[i][c] != dp[i - 1][c]:                      # l'objet i a été pris

Récurrence en une ligne : dp[i][c] = max(dp[i-1][c], dp[i-1][c - poids[i-1]] + valeurs[i-1]). Complexité O(n × W) en temps et mémoire, avec W la capacité ; la reconstruction coûte O(n) en remontant la table. La version gloutonne (tri par ratio valeur/poids) échoue ici et donne un résultat sous-optimal sur certaines instances : c'est l'exemple type de la frontière glouton/DP.

#7. Plus longue sous-séquence communeCopier le lien

Étant donné deux chaînes X et Y, trouver la plus longue séquence de caractères apparaissant dans les deux (dans l'ordre, pas forcément consécutivement).

1def lcs(x, y):2    """Renvoie la plus longue sous-séquence commune de x et y."""3    m, n = len(x), len(y)4    dp = [[0] * (n + 1) for _ in range(m + 1)]5    for i in range(1, m + 1):6        for j in range(1, n + 1):7            if x[i - 1] == y[j - 1]:8                dp[i][j] = dp[i - 1][j - 1] + 19            else:10                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])11 12    # Reconstruction en remontant depuis (m, n)13    seq = []14    i, j = m, n

La récurrence se lit comme une décision : si les derniers caractères coincident, ils appartiennent à la sous-séquence ; sinon l'un des deux est écarté. Complexité O(m × n), utilisée du diff de code à la comparaison d'ADN.

#8. Exercices avec vérificationCopier le lien

1. Chaîne de multiplication de matrices : étant donné les dimensions p de n matrices, parenthéser le produit pour minimiser les multiplications scalaires. État : dp[i][j] = coût minimal pour le produit des matrices i à j. Vérification : pour p = [10, 30, 5, 60], le coût optimal vaut 4500 (parenthésage ((M1×M2)×M3)).
2. Chemins dans une grille : compter les chemins du coin haut-gauche vers le coin bas-droit d'une grille à déplacements droite/bas uniquement. Vérification : grille 3×3 avec un obstacle central, la réponse est 2.
3. Récurrence à écrire d'abord : pour chaque exercice, énoncez l'état, la récurrence et les cas de base sur papier avant de coder ; c'est l'ordre qui produit 90 % du résultat.

#9. Pièges fréquentsCopier le lien

• Ordre de remplissage : chaque case ne doit dépendre que de cases déjà calculées ; inverser l'ordre des boucles du rendu de monnaie change le problème résolu (permettre plusieurs usages d'une même pièce ou non).
• Espace d'états trop large : la mémoïsation sur un produit de dimensions énorme explose en mémoire ; bordez l'espace ou cherchez un état plus fin.
• Double comptage : une transition ambiguë où deux chemins mènent au même état compte deux fois la même solution ; l'état doit caractériser exactement ce qui reste à décider.

#Mini-quizCopier le lien