Mémoïsation contre tabulation
Deux façons de mettre en cache les réponses aux sous-problèmes
Mémoïsation contre tabulation est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Pourquoi utiliser un cache
Une récursion naïve refait sans cesse le même travail. La programmation dynamique stocke chaque réponse une seule fois afin que vous ne la recalculiez jamais.
fib(40) # slow: recomputes endlesslySous-problèmes qui se recouvrent
DP s'applique lorsqu'un problème se divise en sous-problèmes qui se recouvrent. Le même cas plus petit apparaît dans de nombreuses branches de la récursion.
fib(5) needs fib(3) twiceDe haut en bas : la mémoïsation
La mémoïsation consiste en une récursion classique à laquelle on ajoute un cache. Vous calculez à la demande et mémorisez le résultat dès la première occurrence de chaque entrée.
memo = {}La mémoïsation facile en Python
Le décorateur lru_cache transforme une récursion lente en DP rapide en une seule ligne, en mettant automatiquement chaque appel en cache.
from functools import lru_cache
@lru_cache(None)
def f(n): ...De bas en haut : la tabulation
La tabulation remplit un tableau en partant des cas les plus petits jusqu'à la réponse, avec une boucle plutôt qu'une récursion.
dp = [0] * (n + 1)Un Fibonacci tabulé
Définissez les valeurs de base, puis laissez chaque cellule lire celles qui sont déjà calculées. Pas de pile d'appels, simplement une boucle claire.
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Même réponse, style différent
La mémoïsation et la tabulation résolvent la même récurrence. Elles ne diffèrent que par leur sens : de haut en bas à la demande, ou de bas en haut dans l'ordre.
Quand privilégier la mémoïsation
Privilégiez la mémoïsation lorsque la récurrence s'écrit naturellement et que vous n'aurez peut-être pas besoin de tous les états.
Quand privilégier la tabulation
Choisissez la tabulation pour les boucles serrées, pour éviter les erreurs de limite de récursion et lorsque vous calculerez de toute façon tout le tableau.
import sys; sys.setrecursionlimit(10**6)Surveiller la limite de récursion
Une récursion mémoïsée profonde peut atteindre la limite de récursion de Python et provoquer un plantage avec un verdict d'erreur d'exécution sur les grandes entrées.
Un coût commun aux deux méthodes
Dans les deux cas, l'accélération vient du fait de résoudre chaque état une seule fois. Le temps total correspond au nombre d'états multiplié par le travail effectué pour chaque état.
Vérification rapide
Quelle méthode remplit un tableau de bas en haut avec une boucle ?
Récapitulatif : deux méthodes, une seule DP
Vous savez maintenant mettre les sous-problèmes en cache de deux façons. La mémoïsation utilise une récursion de haut en bas ; la tabulation parcourt les états de bas en haut. Choisissez celle qui rend le code le plus clair. ✨
Questions Fréquemment Posées
La leçon « Mémoïsation contre tabulation » est-elle gratuite ?
Oui — le texte complet de « Mémoïsation contre tabulation » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Mémoïsation contre tabulation » ?
Deux façons de mettre en cache les réponses aux sous-problèmes Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Mémoïsation contre tabulation » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Mémoïsation contre tabulation
- Définir l’état et la transition
- Escaliers et combinaisons de pièces
- Plus longue sous-séquence croissante