Programmation dynamique en entretien : de la récursion à la mémoïsation et la tabulation

La programmation dynamique est la matière qui fait le plus peur aux candidats. On la décrit comme un art mystérieux réservé aux génies, et beaucoup abandonnent dès qu’un énoncé sent la récursion compliquée. C’est une erreur de perspective. La programmation dynamique n’est pas une inspiration soudaine : c’est une méthode mécanique en trois temps, qui part d’une récursion naïve, repère le travail répété, et l’élimine. Une fois la méthode comprise, la plupart des problèmes dits « difficiles » deviennent une suite d’étapes prévisibles.

Dans ce tutoriel, vous allez gravir cet escalier pas à pas. Vous commencerez par la solution récursive la plus naïve, vous mesurerez pourquoi elle explose, puis vous la transformerez en deux temps : d’abord la mémoïsation, qui garde en mémoire les résultats déjà calculés, ensuite la tabulation, qui reconstruit la solution de bas en haut. Vous finirez sur un problème plus riche, le rendu de monnaie, et sur une méthode générale applicable à tout énoncé.

Ce que vous allez apprendre

• Reconnaître les deux signaux qui trahissent un problème de programmation dynamique.
• Transformer une récursion exponentielle en solution linéaire par mémoïsation.
• Réécrire la même logique en tabulation, puis réduire l’espace utilisé.
• Appliquer une méthode en quatre questions à n’importe quel énoncé.

Ce que vous allez construire

Vous écrirez quatre versions d’un même calcul de la suite de Fibonacci, de la plus lente à la plus efficace, pour voir la méthode à l’œuvre. Puis vous résoudrez le rendu de monnaie minimal, un classique d’entretien. Le livrable réel est la méthode reproductible que vous garderez pour aborder n’importe quel problème de cette famille.

Prérequis

• Python 3.9 ou plus récent — la version 3.9 introduit le décorateur functools.cache utilisé plus bas.
• Comprendre la récursion et les complexités exponentielle et linéaire.
• Idéalement, avoir lu le rappel sur la complexité.
• Temps estimé : environ 40 minutes.

Étape 1 — Reconnaître un problème de programmation dynamique

Avant de coder, apprenez à repérer la famille. Deux signaux, présents ensemble, désignent la programmation dynamique. Le premier est la sous-structure optimale : la solution d’un problème se construit à partir des solutions de sous-problèmes plus petits. Le second est le recouvrement des sous-problèmes : ces sous-problèmes reviennent plusieurs fois au cours du calcul. Quand un énoncé contient une formule du type « le résultat pour n dépend du résultat pour des valeurs plus petites », et que ces valeurs sont recalculées encore et encore, vous tenez un candidat à la programmation dynamique.

La suite de Fibonacci est l’exemple d’école : chaque terme est la somme des deux précédents. La sous-structure optimale est évidente, et le recouvrement aussi, comme nous allons le voir dès qu’on déroule la récursion naïve.

Étape 2 — Partir de la récursion naïve

On commence toujours par la traduction la plus directe de l’énoncé, sans se soucier de l’efficacité. Pour Fibonacci, cela donne une fonction qui s’appelle elle-même deux fois.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))  # 55

Le résultat est correct : fib(10) vaut 55. Mais essayez fib(40) et le programme rame plusieurs secondes. La raison est que le calcul de fib(n - 1) recalcule entièrement fib(n - 2), déjà demandé par ailleurs, et ainsi de suite en cascade. Le nombre d’appels double presque à chaque niveau, ce qui donne une complexité exponentielle, de l’ordre de O(2ⁿ). C’est exactement le symptôme — un même sous-problème recalculé un nombre astronomique de fois — que la programmation dynamique va corriger.

Voir le travail répété : l’arbre des appels

Pour saisir intimement pourquoi la récursion naïve s’effondre, dessinez son arbre des appels sur un petit cas. Calculer le sixième terme appelle le cinquième et le quatrième. Le cinquième appelle à son tour le quatrième et le troisième. Le quatrième est donc demandé deux fois, et chacune de ces demandes redéclenche tout son sous-arbre de calcul. Plus on descend, plus la duplication s’aggrave : le deuxième terme finit recalculé un grand nombre de fois pour une entrée pourtant modeste.

Cette image mentale est précieuse en entretien. Quand vous expliquez à l’examinateur que votre première solution est lente, ne dites pas seulement « c’est exponentiel » : montrez, sur l’arbre, le sous-problème qui revient. Cette démonstration prouve que vous avez identifié la cause exacte — le recouvrement des sous-problèmes — et elle justifie naturellement la solution que vous allez proposer. La mémoïsation consiste précisément à élaguer cet arbre : dès qu’une branche a été calculée une fois, on n’y retourne plus, on lit le résultat dans le carnet. L’arbre touffu devient une simple chaîne, et c’est tout le gain de complexité résumé en une image.

Étape 3 — Mémoïser : se souvenir de haut en bas

La mémoïsation garde la structure récursive mais ajoute un carnet de notes : avant de calculer un sous-problème, on regarde s’il est déjà connu ; après l’avoir calculé, on l’enregistre. On parle d’approche descendante, ou top-down, car on part du grand problème et on descend vers les petits.

def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

print(fib_memo(40))  # 102334155

Le calcul de fib_memo(40) est désormais instantané. Chaque valeur n’est calculée qu’une seule fois et réutilisée ensuite, ce qui ramène la complexité à un temps linéaire en O(n), au prix d’un espace O(n) pour le carnet. Python offre une manière encore plus concise d’obtenir le même effet, grâce au décorateur cache du module functools, disponible depuis la version 3.9.

from functools import cache

@cache
def fib_rapide(n):
    if n < 2:
        return n
    return fib_rapide(n - 1) + fib_rapide(n - 2)

print(fib_rapide(40))  # 102334155

Le décorateur @cache mémorise automatiquement chaque résultat selon les arguments reçus, ce qui revient exactement à notre carnet manuel mais sans une ligne de gestion. C’est l’outil idéal en entretien quand le temps presse, à condition d’expliquer à voix haute ce qu’il fait : un examinateur veut savoir que vous comprenez le mécanisme, pas seulement que vous connaissez le raccourci.

Étape 4 — Tabuler : construire de bas en haut

La tabulation inverse le sens du calcul. Au lieu de partir du grand problème, on remplit un tableau des plus petits sous-problèmes vers les plus grands, jusqu’à atteindre la réponse cherchée. On parle d’approche ascendante, ou bottom-up. Elle évite la récursion et donc le risque de dépassement de pile sur de très grandes entrées.

def fib_table(n):
    if n < 2:
        return n
    precedent, courant = 0, 1
    for _ in range(2, n + 1):
        precedent, courant = courant, precedent + courant
    return courant

print(fib_table(40))  # 102334155

Cette version mérite qu’on s’y attarde, car elle illustre une optimisation fréquente. Pour Fibonacci, on n’a jamais besoin de tout l’historique : seules les deux dernières valeurs comptent. On garde donc deux variables au lieu d’un tableau complet, ce qui fait tomber l’espace de O(n) à O(1) tout en conservant le temps linéaire. En entretien, repérer qu’on peut réduire l’espace de cette manière est un signal de maturité très apprécié.

Étape 5 — Un cas plus riche : le rendu de monnaie

Fibonacci est pédagogique mais simple. Le rendu de monnaie minimal est plus représentatif des énoncés réels : étant donné un ensemble de valeurs de pièces et un montant, quel est le plus petit nombre de pièces pour atteindre ce montant ? La sous-structure optimale est là : le meilleur rendu pour un montant donné se déduit du meilleur rendu pour ce montant moins la valeur de chaque pièce.

def rendu_monnaie(pieces, montant):
    INFINI = float("inf")
    dp = [0] + [INFINI] * montant
    for valeur in range(1, montant + 1):
        for piece in pieces:
            if piece <= valeur and dp[valeur - piece] + 1 < dp[valeur]:
                dp[valeur] = dp[valeur - piece] + 1
    return dp[montant] if dp[montant] != INFINI else -1

print(rendu_monnaie([1, 3, 4], 6))  # 2

Le résultat est 2, car six se rend optimalement avec deux pièces de trois, et non avec une pièce de quatre suivie de deux pièces de un, qui en ferait trois. Le tableau dp mémorise, pour chaque montant intermédiaire, le nombre minimal de pièces ; on le remplit de un jusqu’au montant cible. La complexité est le produit du montant par le nombre de pièces, soit O(montant × nombre de pièces). Remarquez l’usage de l’infini comme valeur de départ : il signale les montants encore inatteignables, et le test final distingue le cas où aucune combinaison n’existe.

Reconstruire la solution, pas seulement son coût

Le rendu de monnaie tel que nous l’avons écrit répond à une question de coût : combien de pièces au minimum ? Mais un examinateur enchaîne souvent avec une variante redoutée : non plus combien, mais lesquelles. Savoir reconstruire la solution réelle, et pas seulement sa valeur optimale, est une compétence qui sépare les candidats préparés des autres.

Le principe est de mémoriser, en même temps que le coût optimal de chaque état, le choix qui l’a produit — ici, la dernière pièce utilisée. Un second tableau enregistre, pour chaque montant, la pièce ajoutée en dernier. Une fois le tableau rempli, on repart du montant cible et on remonte la chaîne des choix : on soustrait la pièce mémorisée, on note cette pièce, et on recommence jusqu’à zéro. Cette technique de remontée, ou backtracking sur la table, s’applique à la plupart des problèmes de programmation dynamique où l’on veut exhiber la solution. En entretien, mentionnez spontanément cette possibilité même si on ne vous la demande pas tout de suite : elle montre que vous voyez le problème dans son ensemble et anticipez la suite probable de la discussion.

Étape 6 — La méthode générale en quatre questions

Quel que soit le problème, la même grille de quatre questions vous mène à la solution. Première question : quel est l’état, c’est-à-dire l’information minimale qui décrit un sous-problème ? Pour le rendu de monnaie, c’est simplement le montant restant. Deuxième question : quelle est la relation de récurrence qui relie un état aux états plus petits ? Troisième question : quels sont les cas de base, les états dont la réponse est connue sans calcul ? Quatrième question : dans quel ordre remplir les états pour que chaque calcul dispose déjà de ses dépendances ? Répondre à ces quatre questions, dans cet ordre, transforme un énoncé intimidant en un programme méthodique. C’est la démarche que les examinateurs veulent vous voir verbaliser.

Pièges fréquents

S’adapter au contexte ouest-africain

La programmation dynamique se travaille à la main bien plus qu’à l’écran. Munissez-vous d’un cahier : dessiner le tableau des états et le remplir case par case ancre la méthode bien mieux que de relire du code. Cette pratique a un avantage local concret : elle ne dépend ni de l’électricité ni de la connexion, et reste possible pendant une coupure. Pour l’entraînement chronométré, téléchargez quelques énoncés quand le réseau est stable et travaillez-les hors ligne. Le jour de l’entretien à distance, le fait d’avoir tracé des dizaines de tableaux sur papier vous rendra la formulation à voix haute naturelle, même sous le stress d’une visioconférence qui peut se figer.

Récapitulatif

Vous avez parcouru l’escalier complet de la programmation dynamique : récursion naïve, mémoïsation descendante, tabulation ascendante, puis optimisation de l’espace. Vous savez reconnaître la famille à ses deux signaux, et vous disposez d’une méthode en quatre questions applicable à tout énoncé. La leçon centrale est que la programmation dynamique n’a rien de magique : c’est l’art d’éliminer le travail répété, une discipline qui se pratique et se maîtrise.

Aide-mémoire

À vous de jouer

Un défi pour appliquer la méthode : un escalier compte n marches, et l’on monte une ou deux marches à la fois. Combien de façons distinctes de monter ? Tentez une solution en tabulation avant de regarder.

def facons_monter(n):
    if n <= 2:
        return n
    avant_dernier, dernier = 1, 2
    for _ in range(3, n + 1):
        avant_dernier, dernier = dernier, avant_dernier + dernier
    return dernier

print(facons_monter(5))  # 8

Tutoriels frères

• Reconnaître les patterns d’algorithmes — pour les problèmes qui ne relèvent pas de la programmation dynamique.
• Structurer sa résolution en direct — la méthode qui encadre toute résolution.

Pour aller plus loin

• Retour au guide principal : réussir les entretiens techniques.
• Documentation Python — module functools (décorateur cache, depuis la 3.9).

Foire aux questions

Mémoïsation ou tabulation : laquelle choisir ?
Les deux donnent la même complexité. La mémoïsation est plus proche de la formulation naturelle du problème et plus rapide à écrire ; la tabulation évite la récursion et permet souvent d’optimiser l’espace. En entretien, commencez par celle qui vous vient le plus naturellement, puis mentionnez l’autre comme alternative.

Le décorateur cache est-il accepté en entretien ?
Oui, à condition d’expliquer ce qu’il fait. Beaucoup d’examinateurs apprécient une solution concise, mais ils veulent s’assurer que vous comprenez le mécanisme sous-jacent. Sachez aussi écrire la mémoïsation à la main au cas où on vous le demande.

Comment éviter de me perdre dans les indices du tableau ?
Définissez explicitement, par écrit, ce que représente chaque case avant de coder. Une phrase comme « dp de i est le nombre minimal de pièces pour le montant i » clarifie toute la suite et évite la plupart des erreurs de bornes.