La programmation dynamique

def fib_compte(n, compteur):
    compteur[0] += 1
    if n <= 1:
        return n
    return fib_compte(n - 1, compteur) + fib_compte(n - 2, compteur)
# n = 10 :       177 appels ; n = 20 :    21 891 ; n = 30 : 2 692 537
# fib_memo :      19 appels ;             39     ;          59  (= 2n - 1)

La version naïve suit $\approx 1,618^n$ (chaque cran de $n$ multiplie par le nombre d'or — c'est la récurrence de Fibonacci appliquée à son propre coût) ; la mémoïsée fait $2n-1$ appels : chaque état est calculé une fois, puis servi depuis le dictionnaire. Le rapport pour $n=30$ : $2692537/59\approx 45000$. (L'instrumentation par compteur — une liste mutée, chapitre 10 — est l'outil de diagnostic à retenir : avant d'optimiser une récursion, compter ses appels distincts et totaux ; un grand écart entre les deux signe le chevauchement, donc un candidat à la mémoïsation.)

(a) Le dernier pas vaut $1$ ou $2$ : $E(n)=E(n-1)+E(n-2)$, $E(0)=E(1)=1$ — Fibonacci décalé ; de bas en haut, $E(10)=89$. (b) On n'entre dans une case que par le haut ou la gauche : $C(i,j)=C(i-1,j)+C(i,j-1)$, $C(0,j)=C(i,0)=1$ (un seul chemin le long d'un bord).

def nb_chemins(p: int, q: int) -> int:
    C = [[1] * q for _ in range(p)]
    for i in range(1, p):
        for j in range(1, q):
            C[i][j] = C[i - 1][j] + C[i][j - 1]
    return C[p - 1][q - 1]

assert nb_chemins(3, 3) == 6          # le BFS du chapitre 13 confirmait déjà

(Deux dénombrements sans optimisation : la programmation dynamique compte aussi — la récurrence additionne au lieu de minimiser, tout le reste est identique ; et $C(i,j)=\left(\genfrac{}{}{0ex}{}{i+j}{i}\right)$ relie la table au triangle de Pascal, qui est… une table de programmation dynamique née trois siècles avant l'informatique.)

Lecture de $N[14]$ : essais $1+N[4]=5$, $1+N[7]=2$, $1+N[13]=5$ — minimum $2$ par la pièce $7$. Reconstruction : $14\stackrel{7}{\to }7\stackrel{7}{\to }0$, rendu $[7,7]$. Le glouton prenait $10$ (laissant $4$, soit $N[4]=4$ pièces — il s'enfermait). Pour $s=20$ : $N[20]=2$ ($10+10$) — le glouton, ici, aurait bon : le système piège ne piège pas partout, et c'est bien pourquoi trois tests ne prouvent rien (chapitre 7). (Remplir une table à la main une fois dans sa vie est le meilleur vaccin contre les indices décalés ; et la ligne « choix » montre que la reconstruction ne coûte presque rien à condition d'y penser pendant le remplissage.)

(a) En traitant les éléments un à un : après l'élément $x$, les sommes atteignables sont celles d'avant, plus celles d'avant décalées de $x$ (prendre ou ne pas prendre $x$ — pas de choix sûr : on garde les deux). (b)

def partition_equilibree(t: list) -> tuple:
    S = sum(t)
    atteignable = [True] + [False] * (S // 2)
    temoin = [None] * (S // 2 + 1)            # l'élément qui a atteint s
    for x in t:
        for s in range(S // 2, x - 1, -1):    # à rebours : x utilisé 1 fois !
            if not atteignable[s] and atteignable[s - x]:
                atteignable[s] = True
                temoin[s] = x
    meilleur = max(s for s in range(S // 2 + 1) if atteignable[s])
    paquet, s = [], meilleur                  # reconstruction par témoins
    while s > 0:
        paquet.append(temoin[s])
        s -= temoin[s]
    return (paquet, meilleur, S - meilleur)

# partition_equilibree([5, 8, 13, 4, 6]) : somme 36, moitié 18
# -> paquet [13, 5] (somme 18) contre [8, 4, 6] (somme 18) : équilibre parfait

(c) Temps $O(n\cdot S)$, mémoire $O(S)$ : polynomial en la valeur $S$, exponentiel en sa taille en bits — « pseudo-polynomial » : très praticable pour des sommes modestes ($n=100$, $S=10^5$ : dix millions d'opérations), impraticable pour des entiers de cinquante chiffres ; le problème général est réputé dur, et cette table est exactement ce qu'on sait faire de mieux en pratique courante. (Le parcours à rebours de la boucle interne est le piège technique : à l'endroit, l'élément $x$ pourrait servir deux fois ($s-x$ déjà mis à jour au même tour) — une ligne d'écart entre « chaque élément au plus une fois » et « réutilisable à volonté », à connaître car les deux variantes existent et se ressemblent trait pour trait.)

(a) Le glouton par fin croissante (optimal pour compter les tâches, prouvé au chapitre 7) choisit $B$, puis $C$, puis $D$ : gain $60$ — en bloquant $A$ et ses $100$. La preuve d'échange du chapitre 7 s'effondre : remplacer une tâche par une autre qui finit plus tôt ne préserve plus le gain. Sous-structure optimale : toujours là ; choix sûr : disparu — cap sur la table. (b) Tâches triées par fin : $B,C,A,D$. Prédécesseurs compatibles (la dernière tâche finissant avant le début) : $p(B)=$ aucune, $p(C)=B$, $p(A)=$ aucune, $p(D)=C$. Récurrence — la tâche $i$ est dans l'optimum ou non :

$$G(B)=\max (0,20)=20;G(C)=\max (20,20+20)=40;$$

$$G(A)=\max (40,100+0)=100;G(D)=\max (100,20+40)=100.$$

Optimum $100$ ; reconstruction depuis $D$ : $G(D)=G(A)$ donc $D$ exclue ; $G(A)\ne G(C)$ donc $A$ prise, saut à $p(A)$ : vide — solution $\{A\}$. (c) Tri $O(n\log n)$, recherche des $p(i)$ par dichotomie (chapitre 5 !) $O(n\log n)$, table $O(n)$ : total $O(n\log n)$. (Le schéma « $\max$(sans moi, moi $+$ meilleur compatible) » est l'un des plus réutilisés de la programmation dynamique — et l'exemple type du programme pour confronter glouton et table sur le même énoncé : seule la fonction objectif a changé, et tout l'édifice de preuve du glouton s'est écroulé.)

(a) Comparer les derniers caractères : s'ils sont égaux, ils peuvent conclure la sous-suite commune ; sinon, l'un des deux au moins n'en fait pas partie :

$$L(i,j)=\{\begin{array}{ll}0& \text{si }i=0\text{ ou }j=0,\\ L(i-1,j-1)+1& \text{si }{u}_i=v_j,\\ \max (L(i-1,j),L(i,j-1))& \text{sinon.}\end{array}$$

(b)

def plsc(u: str, v: str) -> str:
    n, m = len(u), len(v)
    L = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if u[i - 1] == v[j - 1]:
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                L[i][j] = max(L[i - 1][j], L[i][j - 1])
    i, j, mot = n, m, []                      # reconstruction, à rebours
    while i > 0 and j > 0:
        if u[i - 1] == v[j - 1]:
            mot.append(u[i - 1]); i -= 1; j -= 1
        elif L[i - 1][j] >= L[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(reversed(mot))

# plsc("BATEAU", "TABLEAU") -> "BEAU" (longueur 4)

$L(6,7)=4$ : la reconstruction rend la sous-suite "BEAU" (et "TEAU" marche aussi — l'optimum n'est pas unique, la reconstruction en choisit un selon ses départages). (c) C'est l'algorithme de diff et des gestionnaires de versions : la PLSC de deux fichiers est leur partie commune maximale, et tout le reste — affiché en $+$ et $-$ — est le changement ; deux mille ans de copistes auraient aimé l'avoir. (Coût $O(nm)$ temps et mémoire : la table à deux indices est le format standard des problèmes à deux séquences — et le candidat parfait pour l'économie de mémoire de l'exercice 9, si l'on accepte de perdre la reconstruction.)

(a) Même grille que la PLSC, autre récurrence — trois gestes possibles sur les derniers caractères :

$$D(i,0)=i,D(0,j)=j,$$

$$D(i,j)=\min (\underset{\text{supprimer }{u}_i}{\underbrace{D(i-1,j)+1}},\underset{\text{inseˊrer }{v}_j}{\underbrace{D(i,j-1)+1}},\underset{\text{substituer (ou rien)}}{\underbrace{D(i-1,j-1)+[u_i\ne v_j]}}).$$

(b)

def levenshtein(u: str, v: str) -> int:
    n, m = len(u), len(v)
    D = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        D[i][0] = i
    for j in range(m + 1):
        D[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cout = 0 if u[i - 1] == v[j - 1] else 1
            D[i][j] = min(D[i - 1][j] + 1, D[i][j - 1] + 1,
                          D[i - 1][j - 1] + cout)
    return D[n][m]

assert levenshtein("CHAT", "CHIEN") == 3      # A->I, T->E, +N

Trois opérations : substituer A en I, T en E, insérer N — et la table prouve qu'on ne peut pas faire mieux, ce qu'aucun bricolage manuel ne garantit. (c) Les correcteurs orthographiques (proposer les mots du dictionnaire à distance $\le 2$ de la faute) ; la bio-informatique (aligner deux séquences d'ADN, où insertions et mutations sont les opérations biologiques — les matrices de ce chapitre y tournent sur des génomes entiers). (PLSC et Levenshtein sont sœurs : même grille de préfixes, récurrences cousines — apprendre à reconnaître la famille « deux séquences $\to$ table $(i,j)$ » fait gagner la moitié du travail de conception, l'étape 1 de la méthode.)

(a) Le plus court chemin de $i$ à $j$ n'utilisant que des intermédiaires $<k+1$ passe par le sommet $k$, ou non :

$$D_{k+1}(i,j)=\min (D_k(i,j),D_k(i,k)+D_k(k,j)),D_0=\text{matrice des arcs}.$$

Sous-structure optimale sur un paramètre inattendu — l'ensemble des intermédiaires autorisés : c'est l'étape 1 de la méthode dans toute sa créativité. (b)

def floyd_warshall(M: list) -> list:
    """M : matrice des poids (inf si pas d'arc, 0 en diagonale). En place."""
    n = len(M)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if M[i][k] + M[k][j] < M[i][j]:
                    M[i][j] = M[i][k] + M[k][j]
    return M

INF = float("inf")
M = [[0, 2, 3], [INF, 0, INF], [INF, -2, 0]]   # s, a, b numérotés 0, 1, 2
floyd_warshall(M)
assert M[0][1] == 1                             # s -> b -> a : 3 - 2 = 1 !

Là où Dijkstra mentait en silence (chapitre 14 : il figeait $a$ à $2$), Floyd-Warshall rend $1$ : sa récurrence n'utilise jamais l'argument « le reste du chemin pèse $\ge 0$ » — les poids négatifs lui sont indifférents, tant qu'aucun cycle de poids total négatif n'existe (sinon « la distance » elle-même n'a plus de sens : on tournerait pour gagner). (c) Floyd-Warshall : $O(n^3)$, trois lignes, toutes les paires, poids négatifs admis. $n\times$ Dijkstra : $O(n\cdot n^2)=O(n^3)$ aussi en version naïve — mais $O(n(n+m)\log n)$ avec une bonne file : mieux sur les graphes creux, et poids positifs exigés. Règle pratique : petit graphe dense ou poids négatifs $\to$ Floyd-Warshall ; grand graphe creux positif $\to$ Dijkstra répété. (La boucle sur $k$ est extérieure — l'inverser avec $i,j$ casse la récurrence : l'ordre de remplissage est un théorème, pas un style ; le vérifier fait partie de l'étape 3 de la méthode.)

(a) $F[k]$ ne dépend que de $F[k-1]$ et $F[k-2]$ : deux variables glissantes — a, b = b, a + b — et la table disparaît. (b) $D[i][\cdot ]$ ne dépend que de $D[i-1][\cdot ]$ : conserver la ligne précédente et la courante,

def levenshtein_2lignes(u: str, v: str) -> int:
    if len(v) > len(u):
        u, v = v, u                            # la ligne courte en mémoire
    prec = list(range(len(v) + 1))
    for i in range(1, len(u) + 1):
        cour = [i] + [0] * len(v)
        for j in range(1, len(v) + 1):
            cout = 0 if u[i - 1] == v[j - 1] else 1
            cour[j] = min(prec[j] + 1, cour[j - 1] + 1, prec[j - 1] + cout)
        prec = cour
    return prec[len(v)]

— même résultat que la table pleine sur tous les tests, mémoire $O(\min (n,m))$ au lieu de $O(nm)$ : pour deux chromosomes de $10^6$ caractères, c'est la différence entre $8$ mégaoctets et $8$ téraoctets. (c) Le sacrifice : la reconstruction. Remonter le chemin des choix exige de relire les cases abandonnées — la valeur optimale survit, la solution optimale non. Réponses possibles : garder la table pleine quand elle tient (la voie simple) ; recalculer localement à rebours ; ou les algorithmes « diviser pour régner » qui retrouvent le chemin en mémoire réduite au prix d'un facteur $2$ de temps (hors programme, mais l'existence mérite d'être sue : l'arbitrage temps-mémoire-solution est un triangle, pas un segment). (L'enjeu de mémoire est celui que le programme nomme explicitement : une programmation dynamique se dimensionne — états, octets, et ce qu'on veut à la fin — avant de coder, comme les complexités en espace du chapitre 10.)

(a) Glouton : la preuve d'échange du chapitre 7 passe (toute pièce se rembourse en pièces plus petites sans allonger le rendu) — choix local sûr établi. (b) Table : le contre-exemple $\{10,7,1\}$ tue tout choix sûr ; la récurrence du cours, elle, ne suppose rien du système. (c) Glouton : « par fin croissante », prouvé par échange au chapitre 7 — la tâche qui finit le plus tôt laisse le plus de place, quel que soit le reste. (d) Table : l'exercice 5 — le gain casse la preuve d'échange, le schéma $\max$(sans moi, moi $+$ compatible) s'impose. (e) Glouton : Dijkstra est un glouton prouvé (chapitre 14 — figer le minimum est un choix local sûr, et sa preuve est exactement un argument d'échange sur les chemins). (f) Table : Floyd-Warshall — le choix sûr de Dijkstra meurt avec les poids négatifs, la récurrence sur les intermédiaires survit. Le motif est constant : sous-structure optimale partout ; le glouton chaque fois qu'un échange se prouve ; la table dès qu'un contre-exemple le réfute — et le banc de force brute pour départager les jours de doute. (C'est la mise en rapport que demande le programme, et une grille de lecture pour toute l'algorithmique d'optimisation : les deux méthodes ne s'opposent pas, elles s'étagent — le glouton est une programmation dynamique dont le $\min$ s'est réduit à un seul terme, certificat à l'appui.)