⌂  Menu général
Support des 4 séances du chapitre « Programmation dynamique ». Il sert à la fois de support de projection en classe et de support de révision à la maison : cliquez sur « Voir la réponse » sous chaque exercice pour afficher le corrigé.
Le principe (Richard Bellman, 1950s) : la PD s'applique quand un problème présente une sous-structure optimale (la solution optimale se construit à partir de solutions optimales de sous-problèmes) et des sous-problèmes qui se chevauchent (le même sous-problème revient plusieurs fois). On le résout une seule fois et on mémorise le résultat — en descendant (mémoïsation, récursif) ou en montant (itératif, tableau rempli du plus petit cas vers le plus grand).

Séance 1 — Comprendre le principe

Fibonacci : de la récursivité naïve à la programmation dynamique

Durée : 2hMémoïsationAscendante

1 fib_mem(n) — approche descendante

On mémorise chaque résultat dans un tableau memo au fur et à mesure des calculs.

Voir la réponse 
def fib_mem(n):
    memo = [0] * (n + 1)
    def f_mem(k):
        if k == 0 or k == 1:
            memo[k] = k
            return k
        elif memo[k] > 0:
            return memo[k]
        else:
            memo[k] = f_mem(k - 1) + f_mem(k - 2)
            return memo[k]
    return f_mem(n)
memo[k] > 0 fonctionne comme test "déjà calculé" seulement parce que F(0)=0 est un cas de base à part.

2 fib_asc(n) — approche ascendante

On construit le tableau des résultats de F0 à Fn, sans aucune récursivité.

Voir la réponse 
def fib_asc(n):
    if n < 2:
        return n
    tab = [0] * (n + 1)
    tab[1] = 1
    for i in range(2, n + 1):
        tab[i] = tab[i - 1] + tab[i - 2]
    return tab[n]

3 chemins(n, m) — dénombrement 2D

Nombre de chemins sur une grille n×m, en se déplaçant uniquement à droite ou en bas.

Voir la réponse 
def chemins(n, m):
    grille = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1): grille[i][0] = 1
    for j in range(m + 1): grille[0][j] = 1
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            grille[i][j] = grille[i-1][j] + grille[i][j-1]
    return grille[n][m]

assert chemins(2, 2) == 6

🎯 Défi bonus

Comparer le nombre d'appels de fib_recursif et fib_mem pour n=25 (compteur global).

Séance 2 — Rendu de monnaie

L'un des deux exemples cités explicitement par le programme officiel

Durée : 2hOptimisationReconstruction de solution

1 Version récursive naïve

Voir la réponse 
def rendu_monnaie(pieces, s):
    if s == 0:
        return 0
    r = s
    for p in pieces:
        if p <= s:
            r = min(r, 1 + rendu_monnaie(pieces, s - p))
    return r
Pour rendu_monnaie([1,2], 3) : sur 7 appels au total, s=1 est calculé 2 fois et s=0 trois fois.

2 Version ascendante

Voir la réponse 
def rendu_monnaie_dyn(pieces, s):
    nb = [0] * (s + 1)
    for n in range(1, s + 1):
        nb[n] = n
        for p in pieces:
            if p <= n:
                nb[n] = min(nb[n], 1 + nb[n - p])
    return nb[s]
Pour [1,6,10] et s=12 : nb = [0,1,2,3,4,5,1,2,3,4,1,2,2]. Résultat : 2 pièces (6+6).

3 Reconstruction de la solution optimale

Voir la réponse 
def rendu_monnaie_solution(pieces, s):
    nb = [n for n in range(s + 1)]
    sol = [[1] * n for n in range(s + 1)]
    sol[0] = []
    for n in range(1, s + 1):
        for p in pieces:
            if p <= n and 1 + nb[n - p] < nb[n]:
                nb[n] = 1 + nb[n - p]
                sol[n] = sol[n - p].copy()
                sol[n].append(p)
    return sol[s]

💡 Glouton vs optimal

Avec {1, 3, 4} pour la somme 6 : le glouton prend 4+1+1 = 3 pièces, alors que 3+3 = 6 n'en nécessite que 2. Le glouton n'est pas toujours optimal !

🎯 Défi bonus — Le sac à dos (0/1)

Maximiser la valeur transportée sans dépasser une capacité W, chaque objet pris au plus une fois.

Voir la réponse 
def sac_a_dos(poids, valeurs, W):
    N = len(poids)
    DP = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(1, N + 1):
        for w in range(W + 1):
            DP[i][w] = DP[i-1][w]
            if poids[i-1] <= w:
                DP[i][w] = max(DP[i][w], valeurs[i-1] + DP[i-1][w - poids[i-1]])
    return DP[N][W]

assert sac_a_dos([2,3,4], [3,4,5], 5) == 7

Séance 3 — Pyramide de nombres

Un exemple très progressif : représenter, valider, scorer, puis optimiser

Durée : 2hSous-structure optimaleComplexité O(n²)

1-2 est_chemin / score

Voir la réponse 
def est_chemin(ch, p):
    if len(ch) != len(p) or ch[0] != 0:
        return False
    for i in range(len(ch) - 1):
        if not (ch[i+1] == ch[i] or ch[i+1] == ch[i] + 1):
            return False
    return True

def score(ch, p):
    return sum(p[i][ch[i]] for i in range(len(p)))

3 calcule_score_max — récursif naïf

score_max(i,j) = p[i][j] + max(score_max(i+1,j), score_max(i+1,j+1)), cas de base au dernier niveau.

Voir la réponse 
def calcule_score_max(p, i=0, j=0):
    if i == len(p) - 1:
        return p[i][j]
    gauche = calcule_score_max(p, i+1, j)
    droite = calcule_score_max(p, i+1, j+1)
    return p[i][j] + max(gauche, droite)

4 prog_dyn — PD ascendante

Voir la réponse 
def prog_dyn(p):
    n = len(p)
    s = [list(niveau) for niveau in p]
    for i in range(n - 2, -1, -1):
        for j in range(len(s[i])):
            s[i][j] = p[i][j] + max(s[i+1][j], s[i+1][j+1])
    return s[0][0]
Complexité : au niveau i il y a i+1 éléments, donc 1+2+...+n ≈ n²/2 opérations → O(n²), contre O(2ⁿ) pour le récursif naïf.

🎯 Défi bonus — Coupe de barres d'acier

Maximiser le revenu en coupant une barre de longueur n, chaque longueur i ayant un prix pi.

Voir la réponse 
def revenu_barre_dyn_asc(n):
    prix = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
    tab = [0] * (n + 1)
    for m in range(1, n + 1):
        r_max = float('-inf')
        for i in range(1, m + 1):
            r_max = max(r_max, prix[i] + tab[m - i])
        tab[m] = r_max
    return tab[n]
Même structure que le rendu de monnaie (séance 2), mais on maximise au lieu de minimiser.

Séance 4 — Alignement de séquences

Le 2e exemple cité par le programme officiel (bio-informatique)

Durée : 2hTableau 2DNeedleman-Wunsch
On aligne deux mots avec des trous (-), sans jamais changer l'ordre des lettres ni aligner deux trous ensemble. Score : Match +1, Mismatch -1, Gap -1.

1 aligne(s1, s2)

sc[i][j] = score maximal d'alignement des i premières lettres de s1 avec les j premières de s2.

Voir la réponse 
def aligne(s1, s2):
    n1, n2 = len(s1), len(s2)
    sc = [[0] * (n2 + 1) for _ in range(n1 + 1)]
    for i in range(1, n1 + 1): sc[i][0] = -i
    for j in range(1, n2 + 1): sc[0][j] = -j
    for i in range(1, n1 + 1):
        for j in range(1, n2 + 1):
            s = max(-1 + sc[i-1][j], -1 + sc[i][j-1])
            if s1[i-1] == s2[j-1]:
                sc[i][j] = max(s, 1 + sc[i-1][j-1])
            else:
                sc[i][j] = max(s, -1 + sc[i-1][j-1])
    return sc[n1][n2]

assert aligne("CHAT", "CAT") == 2
Tableau pour CHAT/CAT :
    -  C  A  T
-  0 -1 -2 -3
C -1  1  0 -1
H -2  0  0  0
A -3 -1  1  0
T -4 -2  0  2

2 affiche(s1, s2, sc)

Voir la réponse 
def affiche(s1, s2, sc):
    print(" ", end="")
    for c in s2: print('{:>3}'.format(c), end="")
    print()
    for i in range(len(sc)):
        print('{:>3}'.format(s1[i-1]) if i > 0 else " ", end="")
        for v in sc[i]: print('{:>3}'.format(v), end="")
        print()

🎯 Défis bonus

Bonus 1 — Reconstruire l'alignement optimal

Renvoyer, en plus du score, les deux chaînes alignées (avec '-' pour les gaps), via un second tableau sol.

Bonus 2 — Matrice de similarités (ADN)

Remplacer les scores fixes (+1/-1) par une matrice de similarités sim[car1][car2] et un coût de gap variable.

sim = {'A': {'A': 10, 'G': -1, 'C': -3, 'T': -4}, ...}
gap = -5