10 — Programmation Dynamique : Cours complet

Niveau : Université — Durée : 5h de cours + 5h de TP La programmation dynamique (DP) est la technique reine pour transformer une exploration exponentielle en solution polynomiale.

---

Partie I — Les 2 propriétés fondamentales

1.1 Overlapping subproblems (sous-problèmes qui se recouvrent)

Le même sous-problème est rencontré de nombreuses fois. Exemple : dans fib(5), fib(3) est calculé 2 fois, fib(2) 3 fois.

Diagramme en cours de génération...

Idée clé : calculer chaque sous-problème une seule fois, le stocker, le réutiliser.

1.2 Optimal substructure (sous-structure optimale)

La solution optimale du problème est composée des solutions optimales de ses sous-problèmes.

• Oui : chemin le plus court (sous-chemin d'un plus court chemin est un plus court chemin).
• Non : chemin le plus long dans un graphe (sous-chemin d'un plus long chemin n'est pas nécessairement le plus long).

1.3 Test de recette

Un problème est résoluble par DP ssi : sous-structure optimale (on peut combiner) ET sous-problèmes qui se recouvrent (on économise réellement).

Si seuls des sous-problèmes disjoints existent → c'est du divide & conquer (chapitre 12), la mémoïsation ne sert à rien.

---

Partie II — Memoization (top-down)

2.1 Principe

On écrit la récursion naturelle, et on ajoute un cache (mémorisation). On explore du haut (problème global) vers le bas (sous-problèmes).

def fib_memo(n: int, memo: dict | None = None) -> int:
    if memo is None:
        memo = {}
    if n in memo:              # sous-problème déjà résolu
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

2.2 Complexité

• Temps : nombre de sous-problèmes distincts × coût par sous-problème. Ici O(n) sous-problèmes × O(1) → O(n).
• Mémoire : O(n) pour le cache + O(n) pour la pile d'appels.

2.3 Avantages / inconvénients

---

Partie III — Tabulation (bottom-up)

3.1 Principe

On remplit un tableau de la plus petite instance vers la plus grande. On définit l'ordre d'évaluation et les dépendances.

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

3.2 Complexité

• Temps : O(n) (mêmes sous-problèmes).
• Mémoire : O(n) — et on peut réduire (Partie VIII).

3.3 Top-down vs Bottom-up : comparatif

---

Partie IV — Problèmes classiques

4.1 Fibonacci — déjà vu

Récurrence : dp[i] = dp[i-1] + dp[i-2].

4.2 Knapsack 0/1

On a n objets (poids w[i], valeur v[i]) et un sac de capacité C. Maximiser la valeur.

État : dp[i][c] = valeur max avec les i premiers objets et capacité c.

dp[i][c] = max(
    dp[i-1][c],                       # ne pas prendre l'objet i
    v[i] + dp[i-1][c - w[i]]          # prendre l'objet i (si c >= w[i])
)

def knapsack01(weights, values, C):
    n = len(weights)
    dp = [[0] * (C + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for c in range(C + 1):
            dp[i][c] = dp[i - 1][c]
            if c >= weights[i - 1]:
                dp[i][c] = max(dp[i][c], values[i - 1] + dp[i - 1][c - weights[i - 1]])
    return dp[n][C]

Complexité : O(n·C) temps, O(n·C) mémoire (→ O(C) avec rolling array).

4.3 Coin change (nombre de façons / minimum de pièces)

Minimum de pièces pour un montant A :

dp[a] = min(dp[a - coin]) + 1  pour chaque coin <= a
dp[0] = 0

def coin_change_min(coins, amount):
    INF = float("inf")
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)
    return dp[amount] if dp[amount] != INF else -1

⚠️ Variante "nombre de combinaisons" : il faut itérer d'abord sur les pièces (ordre externe) pour éviter les permutations (1+2 vs 2+1).

4.4 LCS — Longest Common Subsequence

dp[i][j] = LCS de a[:i] et b[:j].

si a[i-1] == b[j-1] : dp[i][j] = 1 + dp[i-1][j-1]
sinon                 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[n][m]

4.5 LIS — Longest Increasing Subsequence

dp[i] = longueur du LIS se terminant à l'index i.

dp[i] = 1 + max(dp[j]) pour j < i et a[j] < a[i]

Variante O(n log n) : avec une suite de "piles" (tails) et recherche dichotomique.

4.6 Edit distance (Levenshtein)

dp[i][j] = distance entre a[:i] et b[:j]. Opérations : insertion, suppression, substitution (coût 1).

si a[i-1]==b[j-1] : dp[i][j] = dp[i-1][j-1]
sinon :             dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

4.7 Matrix chain multiplication

dp[i][j] = coût min pour multiplier A_i...A_j (tailles p₀..pₙ).

dp[i][j] = min_k ( dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j] )

C'est un DP sur intervalles (Partie VI).

4.8 Partition problem

Peut-on partager nums en 2 sous-ensembles de somme égale ?

def can_partition(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for s in range(target, x - 1, -1):   # parcours décroissant = 0/1 !
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

Règle d'or : parcourir l'axe "poids/somme" en décroissant pour du 0/1 (chaque objet une fois), en croissant pour du unbounded (chaque objet à l'infini).

4.9 Rod cutting

Couper une barre de longueur n pour maximiser le revenu (prix par longueur p[i]).

dp[len] = max(p[i] + dp[len - i]) pour i = 1..len

4.10 House robber

Maisons en ligne, on ne peut pas voler 2 maisons adjacentes.

dp[i] = max(dp[i-1], nums[i] + dp[i-2])

---

Partie V — DP sur grilles

5.1 Unique paths

Aller de (0,0) à (n-1, m-1) en ne se déplaçant que vers le bas/droite.

def unique_paths(n, m):
    dp = [[1] * m for _ in range(n)]
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[n-1][m-1]

5.2 Minimum path sum (avec obstacles/poids)

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

5.3 Patterns de transition sur grilles

---

Partie VI — DP sur intervalles

État : dp[i][j] pour un intervalle [i, j]. Transition : essayer tous les points de coupe k.

• Matrix chain : dp[i][j] = min_k(dp[i][k] + dp[k+1][j] + coût).
• Palindrome partitioning : min de coupes pour tout découper en palindromes.
• Burst balloons : maximiser les points en éclatant des ballons.

def max_coin_matrix_chain(p):
    n = len(p) - 1
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n + 1):            # taille de l'intervalle
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float("inf")
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

Ordre d'évaluation crucial : par taille d'intervalle croissante, pas par ligne.

---

Partie VII — DP bitmask

Quand l'état est un ensemble de taille n ≤ 20, on le représente par un bitmask de n bits.

7.1 Traveling Salesman Problem (n ≤ 15-20)

dp[mask][last] = coût minimal du tour visitant exactement les villes de mask
               se terminant à la ville last.
dp[mask | (1<<v)][v] = min(dp[mask][last] + dist[last][v])

def tsp(dist):
    n = len(dist)
    full = (1 << n) - 1
    INF = float("inf")
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0                      # départ ville 0
    for mask in range(1 << n):
        for last in range(n):
            if not (mask >> last) & 1 or dp[mask][last] == INF:
                continue
            for nxt in range(n):
                if (mask >> nxt) & 1:
                    continue
                dp[mask | (1 << nxt)][nxt] = min(
                    dp[mask | (1 << nxt)][nxt],
                    dp[mask][last] + dist[last][nxt])
    return min(dp[full][v] + dist[v][0] for v in range(1, n))

Complexité : O(2ⁿ·n²) au lieu de O(n!) — immense gain pour n ≤ 20.

7.2 Autres usages

• Partition/assignment : affecter des tâches à des personnes.
• Count subsets with given sum.
• Graph Hamiltonian path counting.

---

Partie VIII — Optimisation spatiale

8.1 Rolling array / 1D

Si dp[i][*] ne dépend que de dp[i-1][*], on n'a besoin que de 2 lignes :

def lcs_space(a, b):
    prev = [0] * (len(b) + 1)
    for i in range(1, len(a) + 1):
        cur = [0] * (len(b) + 1)
        for j in range(1, len(b) + 1):
            if a[i-1] == b[j-1]:
                cur[j] = prev[j-1] + 1
            else:
                cur[j] = max(prev[j], cur[j-1])
        prev = cur
    return prev[len(b)]

Mémoire : O(m) au lieu de O(n·m).

8.2 Knapsack 1D (parcours décroissant)

dp = [0] * (C + 1)
for i in range(n):
    for c in range(C, weights[i] - 1, -1):
        dp[c] = max(dp[c], values[i] + dp[c - weights[i]])

La décroissance garantit que l'objet i n'est utilisé qu'une fois.

8.3 Quand peut-on réduire l'espace ?

Condition : la transition n'utilise qu'un nombre constant de lignes/colonnes antérieures. La reconstruction devient alors plus délicate (il faut garder une trace).

---

Partie IX — Reconstruction de la solution

On veut retrouver la séquence optimale, pas seulement sa valeur.

9.1 Technique : tableau de backtrack

On garde un second tableau choice[i][j] qui enregistre la décision prise (ou un tableau parent).

def lcs_with_path(a, b):
    n, m = len(a), len(b)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # reconstruction en remontant
    res = []
    i, j = n, m
    while i > 0 and j > 0:
        if a[i-1] == b[j-1]:
            res.append(a[i-1]); i -= 1; j -= 1
        elif dp[i-1][j] >= dp[i][j-1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(res))

9.2 Knapsack : retrouver les objets choisis

Même principe : remonter depuis dp[n][C], en testant dp[i-1][c] != dp[i][c].

---

Partie X — Patterns de DP : quand utiliser quoi

10.1 Cheat-sheet de reconnaissance

10.2 Séquences vs ensembles

• 2 chaînes → état (i, j).
• 1 chaîne partitionnée → état (i, j) intervalle, transition sur k.
• Sous-ensemble de n ≤ 20 → bitmask.
• Permutation partielle (longueur de suite) → état (i, len).

10.3 Processus de résolution en 4 étapes

1. Définir l'état : quelles variables résument le passé sans perdre d'info ?
2. Écrire la récurrence : lien entre sous-problèmes (choisir "prendre/ne pas prendre", "couper à k", …).
3. Ordre d'évaluation : top-down (memo) ou bottom-up (tab) + ordre des boucles.
4. Complexité : nbre d'états × coût de transition. Puis optimiser l'espace.

---

Partie XI — Pièges fréquents

---

Check-list de maîtrise

• Je sais expliquer overlapping subproblems et optimal substructure.
• Je sais écrire memo (top-down) et tab (bottom-up) pour un même problème.
• Je sais résoudre knapsack 0/1, coin change, LCS, LIS, edit distance, matrix chain.
• Je sais faire un DP sur grille, intervalle et bitmask.
• Je sais optimiser l'espace avec rolling array.
• Je sais reconstruire la solution optimale.
• Je sais justifier la complexité de n'importe quel DP.