Mémoïsation : mettre en cache les résultats récursifs

La version récursive naïve de Fibonacci recalcule plusieurs fois les mêmes valeurs. fib(5) appelle fib(4) et fib(3) ; fib(4) appelle fib(3) et fib(2) — fib(3) est donc calculé deux fois. Cette redondance augmente de manière exponentielle : fib(40) effectue plus d’un milliard d’appels de fonction. La mémoïsation résout ce problème en stockant chaque résultat lors de son premier calcul, afin que les appels suivants le récupèrent en O(1) au lieu de le recalculer.

Ajoutez un dictionnaire memo comme paramètre (ou utilisez une fermeture). Avant d’effectuer le calcul, vérifiez si la réponse se trouve déjà dans le dictionnaire de mémo. Si c’est le cas, renvoyez-la immédiatement. Sinon, calculez-la, stockez-la dans le dictionnaire, puis renvoyez-la. Chaque sous-problème distinct est alors calculé exactement une fois, ce qui transforme O(2^n) en O(n) en temps et en O(n) d’espace pour le dictionnaire de mémo, auquel s’ajoutent O(n) d’espace de pile.

Python fournit @functools.lru_cache(maxsize=None) (également disponible sous la forme @functools.cache depuis Python 3.9) pour automatiser la mémoïsation. L’ajout de ce décorateur au-dessus d’une fonction met en cache tous ses appels en fonction de leurs arguments. maxsize=None signifie que la taille du cache est illimitée : chaque combinaison d’arguments distincte est mise en cache. Cela transforme n’importe quelle fonction récursive en version mémoïsée avec une seule ligne de code.

Le problème 70 de LeetCode, « Escaliers » : vous pouvez monter 1 ou 2 marches à la fois. Combien de façons existe-t-il d’atteindre la marche n ? Il s’agit en réalité de Fibonacci : ways(n) = ways(n-1) + ways(n-2). Cas de base : ways(0) = 1 (une façon de rester au sol) et ways(1) = 1. Avec la mémoïsation, le temps d’exécution est O(n) et l’espace utilisé est O(n).

Le problème 322 de LeetCode, « Rendu de monnaie » : étant donné des valeurs de pièces et un montant cible, trouvez le nombre minimal de pièces. Récursion mémoïsée descendante : dp(amount) = 1 + min(dp(amount - coin)) pour chaque pièce valide. Cas de base : dp(0) = 0. Mettez en cache chaque sous-montant. Si un sous-montant est impossible à obtenir, renvoyez l’infini. La mémoïsation transforme la force brute exponentielle en une complexité temporelle de O(montant × longueur(pièces)).

Le problème 139 de LeetCode, « Découpage de mots » : déterminez si une chaîne peut être segmentée en mots du dictionnaire. La récursion descendante can_break(s, start) essaie chaque préfixe s[start:end] ; s’il se trouve dans le dictionnaire et que can_break(s, end) est vrai, renvoyez vrai. Sans mémoïsation, la complexité est O(2^n) ; avec mémoïsation (en mettant en cache chaque indice de début), elle devient O(n² × L), où L est la longueur maximale d’un mot.

La mémoïsation (descendante) part du problème initial et met en cache les réponses au fur et à mesure qu’elles sont découvertes récursivement. Elle ne résout que les sous-problèmes réellement nécessaires. La tabulation (ascendante) remplit au préalable un tableau, des petits sous-problèmes vers les grands, et résout tous les sous-problèmes sans exception. La mémoïsation est plus facile à déduire d’une solution récursive ; la tabulation évite les limites de profondeur de récursion et la surcharge des appels de fonction.

De nombreux problèmes de DP que la récursion mémoïsée résout en O(n) d’espace peuvent être optimisés davantage jusqu’à O(1) d’espace lorsque seul un nombre fixe de réponses précédentes de sous-problèmes est nécessaire. Pour Fibonacci, seules les deux dernières valeurs comptent. Il en va de même pour les escaliers. Deux variables glissantes remplacent l’intégralité du dictionnaire de mémo ou du tableau.

Il existe trois façons d’implémenter manuellement la mémoïsation. Un dictionnaire global est simple, mais il pollue la portée du module. Une fermeture encapsule le cache dans la fonction, ce qui empêche les fuites, mais nécessite une fonction enveloppe. @lru_cache est la solution la plus élégante : un seul décorateur remplace tout le code répétitif. Lors d’un entretien, commencez par @lru_cache, sauf si l’interviewer demande explicitement une implémentation manuelle.

La mémoïsation n’accélère que les problèmes présentant des sous-problèmes qui se chevauchent — c’est-à-dire les cas où le même sous-problème est calculé plusieurs fois. Si chaque sous-problème est unique (comme lors d’un simple parcours d’arbre où chaque nœud est visité exactement une fois), la mémoïsation ajoute une surcharge sans apporter de bénéfice. Elle ne peut pas non plus résoudre les problèmes où l’arbre récursif est exponentiel par rapport au nombre de sous-problèmes distincts plutôt qu’à leur réutilisation ; ceux-ci nécessitent un algorithme entièrement différent.

Appliquez la mémoïsation lorsque : vous disposez d’une solution récursive correcte mais lente en raison de recalculs redondants, la fonction comporte un petit nombre de combinaisons d’arguments distinctes et la valeur renvoyée dépend uniquement des arguments (fonction pure — sans effets secondaires ni état global). Examinez l’espace d’états des sous-problèmes : s’il y a au plus O(n) ou O(n²) états distincts, la mémoïsation transforme une complexité exponentielle en complexité polynomiale.

Évaluez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.

Dans cette leçon, vous avez appris que : la mémoïsation stocke les résultats des sous-problèmes pour éviter les recalculs, transformant une récursion exponentielle en complexité polynomiale ; @functools.lru_cache est l’outil Python idiomatique qui ne nécessite qu’une seule ligne ; et la mémoïsation (descendante) et la tabulation (ascendante) sont les deux styles de DP : la mémoïsation est plus facile à déduire, tandis que la tabulation évite les problèmes de profondeur de pile. Félicitations : vous avez terminé les modules sur la récursion et les tables de hachage !