Quatre façons d’attaquer un problème.

• Écrire la récurrence d’un problème puis la mémoïser ou la tabuler.
• Prouver qu’un glouton est correct (argument d’échange) ou trouver un contre-exemple.
• Élaguer un backtracking pour qu’il termine en secondes au lieu d’années.
• Résoudre les exercices d’algorithmique des concours X-ENS (épreuve d’informatique).

Références : CLRS chapitres 15-16, Algorithm Design (Kleinberg-Tardos), sujets d’informatique du concours Centrale/Mines/X.

Une récurrence T(n) = a·T(n/b) + O(n^d) se résout ainsi : si a < b^d → O(n^d) ; si a = b^d → O(n^d log n) ; si a > b^d → O(n^{log_b a}). Tri fusion : a = 2, b = 2, d = 1 → O(n log n). Recherche dichotomique : a = 1, b = 2, d = 0 → O(log n). Multiplication de Karatsuba : 3 produits de taille n/2 au lieu de 4, a = 3, b = 2, d = 1 → O(n^1,585) : c’est ainsi que Python multiplie les grands entiers. Strassen fait de même pour les matrices (7 produits au lieu de 8 → O(n^2,807)).

1. Définir l’état : « escalier(n) = nombre de façons de monter n marches ». L’état doit contenir exactement l’information nécessaire pour la suite.
2. Écrire la récurrence : escalier(n) = escalier(n−1) + escalier(n−2) + escalier(n−3), avec les cas de base.
3. Choisir : mémoïsation (récursif + cache, simple, ordre automatique) ou tabulation (itératif, plus rapide, mémoire contrôlable).
4. Compter : nombre d’états × coût par état = complexité. Ici n états × O(1) = O(n) au lieu de O(3ⁿ).

La programmation dynamique s’applique quand le problème a une sous-structure optimale (la solution se construit à partir de solutions de sous-problèmes) et des sous-problèmes qui se chevauchent (sinon, diviser pour régner suffit).

Pour la planification : soit une solution optimale O qui ne commence pas par l’activité a₁ qui finit le plus tôt. Remplaçons la première activité de O par a₁ : comme a₁ finit plus tôt, elle est compatible avec le reste de O. On obtient une solution optimale qui commence par a₁. Par récurrence sur le reste, le glouton est optimal. Cet « échange » sans perte est la structure de toutes les preuves de gloutons (Huffman, Kruskal, Dijkstra). Quand l’échange peut faire perdre quelque chose — rendu de monnaie avec pièces {1, 3, 4}, sac à dos 0/1 — le glouton échoue et il faut la programmation dynamique.

1. Vérifier tôt : ne pas remplir toute la grille avant de tester ; refuser un candidat dès qu’il viole une contrainte.
2. Choisir la variable la plus contrainte (MRV : minimum remaining values) : une case à 1 candidat se remplit sans risque ; une case à 0 candidat fait rebrousser immédiatement.
3. Ordonner les valeurs : essayer d’abord celles qui contraignent le moins les voisins (LCV).

Sans ces leviers, un sudoku difficile prend des heures ; avec, des millisecondes. Le backtracking est la base de la résolution de contraintes (CSP), de SAT (module L17) et de la planification. Il est exponentiel dans le pire cas — mais le pire cas est rare quand l’élagage est bon.

def nb_facons(pieces, montant):
    f = [1] + [0] * montant                      # f[m] : façons avec les pièces vues jusqu'ici
    for p in pieces:                             # pièces à l'extérieur : chaque combinaison comptée une fois
        for m in range(p, montant + 1): f[m] += f[m - p]
    return f[montant]

Inverser les boucles (montant à l’extérieur) compterait les suites ordonnées : 9 au lieu de 4 pour le premier test.

def segmenter(texte, dico):
    n = len(texte); prec = [None] * (n + 1); ok = [False] * (n + 1); ok[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if ok[j] and texte[j:i] in dico: ok[i] = True; prec[i] = j; break
    if not ok[n]: return None
    mots, i = [], n
    while i > 0: mots.append(texte[prec[i]:i]); i = prec[i]
    return mots[::-1]

def couverture(intervalles, L):
    pos, n, i = 0, 0, 0; I = sorted(intervalles)
    while pos < L:
        loin = pos
        while i < len(I) and I[i][0] <= pos: loin = max(loin, I[i][1]); i += 1
        if loin == pos: return -1
        pos = loin; n += 1
    return n

def inversions(t):
    def rec(t):
        if len(t) <= 1: return t, 0
        m = len(t) // 2; g, a = rec(t[:m]); d, b = rec(t[m:]); r, i, j, inv = [], 0, 0, a + b
        while i < len(g) and j < len(d):
            if g[i] <= d[j]: r.append(g[i]); i += 1
            else: r.append(d[j]); j += 1; inv += len(g) - i
        return r + g[i:] + d[j:], inv
    return rec(list(t))[1]
def reines(n):
    cols, d1, d2 = set(), set(), set()
    def _rec(l):
        if l == n: return 1
        total = 0
        for c in range(n):
            if c in cols or l + c in d1 or l - c in d2: continue
            cols.add(c); d1.add(l + c); d2.add(l - c)
            total += _rec(l + 1)
            cols.discard(c); d1.discard(l + c); d2.discard(l - c)
        return total
    return _rec(0)

n, m = len(grille), len(grille[0])
libre = lambda i, j: grille[i][j] != "#"
N = [[0] * m for _ in range(n)]; N[0][0] = 1
for i in range(n):
    for j in range(m):
        if not libre(i, j): N[i][j] = 0; continue
        if i: N[i][j] += N[i - 1][j]
        if j: N[i][j] += N[i][j - 1]
print("chemins :", N[n - 1][m - 1])

INF = float("inf")
C = [[INF] * m for _ in range(n)]; C[0][0] = couts[0][0]
for i in range(n):
    for j in range(m):
        if not libre(i, j) or (i, j) == (0, 0): continue
        C[i][j] = couts[i][j] + min(C[i - 1][j] if i else INF, C[i][j - 1] if j else INF)
i, j, chemin = n - 1, m - 1, []
while (i, j) != (0, 0):
    chemin.append((i, j))
    if i and C[i - 1][j] <= (C[i][j - 1] if j else INF): i -= 1
    else: j -= 1
chemin.append((0, 0)); chemin.reverse()
print("coût min :", C[n - 1][m - 1], chemin)
for i in range(n):
    print("".join("*" if (i, j) in chemin else grille[i][j] for j in range(m)))

appels = 0
def naif(n):
    global appels; appels += 1
    if n == 0: return 0
    return max(p(k) + naif(n - k) for k in range(1, n + 1))
print(naif(20), "appels :", appels)         # 2^20 environ

from functools import lru_cache
@lru_cache(None)
def memo(n):
    return 0 if n == 0 else max(p(k) + memo(n - k) for k in range(1, n + 1))
print(memo(20), memo(200))

def tabule(n):
    R, choix = [0] * (n + 1), [0] * (n + 1)
    for l in range(1, n + 1):
        for k in range(1, l + 1):
            if p(k) + R[l - k] > R[l]: R[l], choix[l] = p(k) + R[l - k], k
    morceaux, l = [], n
    while l: morceaux.append(choix[l]); l -= choix[l]
    return R[n], morceaux
print(tabule(20))

Chaque découpage correspond à un choix « couper ou non » à chacune des n−1 positions : 2ⁿ⁻¹. La PD n’a que n états, chacun examinant n choix : O(n²). C’est la différence entre 5·10⁵ et 400 pour n = 20, entre l’âge de l’univers et une milliseconde pour n = 100.

def tsp_backtracking(V):
    n = len(V); meilleur = [float("inf"), None]
    def rec(chemin, longueur, restants):
        if longueur >= meilleur[0]: return                           # élagage par borne
        if not restants:
            total = longueur + d(V[chemin[-1]], V[chemin[0]])
            if total < meilleur[0]: meilleur[0], meilleur[1] = total, list(chemin)
            return
        for v in sorted(restants, key=lambda v: d(V[chemin[-1]], V[v])):   # les proches d'abord
            chemin.append(v); rec(chemin, longueur + d(V[chemin[-2]], V[v]), restants - {v}); chemin.pop()
    rec([0], 0.0, set(range(1, n))); return meilleur[0]

def tsp_held_karp(V):
    n = len(V); INF = float("inf")
    C = {(1, 0): 0.0}                                                # (masque, dernière) → coût
    for masque in range(1, 1 << n):
        if not masque & 1: continue
        for j in range(1, n):
            if not masque & (1 << j) or (masque, j) in C: continue
            prev = masque ^ (1 << j)
            C[(masque, j)] = min((C.get((prev, k), INF) + d(V[k], V[j]) for k in range(n) if prev & (1 << k)), default=INF)
    plein = (1 << n) - 1
    return min(C[(plein, j)] + d(V[j], V[0]) for j in range(1, n))

def tsp_heuristique(V):
    n = len(V); t = [0]; restants = set(range(1, n))
    while restants:                                                   # plus proche voisin
        v = min(restants, key=lambda v: d(V[t[-1]], V[v])); t.append(v); restants.remove(v)
    def longueur(t): return sum(d(V[t[i]], V[t[(i + 1) % n]]) for i in range(n))
    ameliore = True
    while ameliore:                                                   # 2-opt : décroiser deux arêtes
        ameliore = False
        for i in range(1, n - 1):
            for j in range(i + 1, n):
                if d(V[t[i-1]], V[t[j]]) + d(V[t[i]], V[t[(j+1) % n]]) < d(V[t[i-1]], V[t[i]]) + d(V[t[j]], V[t[(j+1) % n]]):
                    t[i:j+1] = reversed(t[i:j+1]); ameliore = True
    return longueur(t)

V = villes(10)
print("exact (backtracking) :", round(tsp_backtracking(V), 4))
print("exact (Held-Karp)    :", round(tsp_held_karp(V), 4))
print("heuristique 2-opt    :", round(tsp_heuristique(V), 4))
print("n = 200, 2-opt       :", round(tsp_heuristique(villes(200)), 3))

Held-Karp est en O(2ⁿ n²) : exponentiel, mais infiniment mieux que n! (pour n = 20 : 4·10⁸ contre 2·10¹⁸). Le TSP est NP-difficile : on ne connaît pas d’algorithme polynomial et on conjecture qu’il n’en existe pas (P ≠ NP, module L23). En pratique, les heuristiques (2-opt, Lin-Kernighan, recuit simulé) donnent des tours à 2-3 % de l’optimal pour des millions de villes, et les solveurs exacts (Concorde) résolvent des instances de 85 900 villes par séparation-évaluation.