0Pricing
DSA Interview Prep · Leçon

DP descendante avec mémoïsation

Ajoutez un dictionnaire de mémoïsation à une solution récursive pour éliminer les appels en double, et utilisez @lru_cache avec un minimum de code.

DP descendante avec mémoïsation est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 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 DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.

DP descendante : l'idée de la mémoïsation

La DP descendante part de la solution récursive originale et lui ajoute la mémoïsation : un cache qui stocke le résultat de chaque sous-problème lors de son premier calcul. Lors des appels suivants avec les mêmes arguments, le résultat en cache est renvoyé immédiatement, sans récursion. Cela transforme une récursion naïve en O(2^n) en une solution en O(n), avec un minimum de modifications du code — souvent, il suffit d'ajouter 2 ou 3 lignes à une solution récursive existante.

# Top-down approach:
# 1. Write the recursive solution (natural but slow)
# 2. Add a memo dict to cache results
# 3. Before recursing, check if the result is cached
# 4. Before returning, store the result in the cache

# This is also called 'memoization' (US spelling)
# 'memoize' means 'to remember', not 'memorize'

# The cache key is the function arguments
# For fib: key is n
# For 2D DP: key is (i, j)
# For 3D DP: key is (i, j, k)
print('Top-down = recursion + memo cache')

Fibonacci avec mémoïsation

L'ajout d'un dictionnaire de mémoïsation à la récursion naïve de Fibonacci réduit le temps de O(2^n) à O(n). Le premier appel à fib(k) calcule et stocke le résultat. Tous les appels suivants pour le même k renvoient instantanément la valeur mise en cache. La complexité spatiale est de O(n) pour le dictionnaire de mémoïsation, à laquelle s'ajoute O(n) pour la pile d'appels. Comparez le nombre d'appels : sans mémoïsation, fib(30) effectue environ 2 millions d'appels ; avec mémoïsation, exactement 30 appels.

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

# Verify speed improvement:
print(fib_memo(30))   # fast!
print(fib_memo(50))   # still fast
print(fib_memo(100))  # no problem

# Without memo, fib_naive(50) would take minutes
# With memo: each of the 50 sub-problems computed once

Utiliser @functools.lru_cache

Le décorateur Python @functools.lru_cache(maxsize=None) (ou son alias @cache dans Python 3.9 et les versions ultérieures) mémoïse automatiquement une fonction en fonction de ses arguments. C'est la manière la plus simple d'ajouter une DP descendante lors d'un entretien : écrivez la solution récursive, ajoutez le décorateur, et c'est terminé. Le décorateur met tous les résultats en cache dans un dictionnaire indexé par les arguments de la fonction, qui doivent être compatibles avec le hachage (pas de listes — utilisez plutôt des tuples).

import functools

@functools.lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

print(fib(50))   # 12586269025
print(fib(100))  # works instantly

# Clear cache between tests if needed:
fib.cache_clear()

# Python 3.9+ shorthand:
# from functools import cache
# @cache
# def fib(n): ...

print(fib.cache_info())  # shows hits, misses, maxsize, currsize

Rendu de monnaie descendant

Rendu de monnaie (LeetCode #322) : étant donné des valeurs de pièces et un montant cible, trouvez le nombre minimal de pièces nécessaires. La formulation récursive consiste, pour chaque pièce, à la prendre et à résoudre le problème pour le montant restant, puis à conserver le minimum. Mémoïsez en fonction du montant pour éviter les recalculs. Cas de base : amount=0 nécessite 0 pièce ; un montant impossible renvoie l'infini (ou -1 après la récursion).

import functools

def coin_change_top_down(coins, amount):
    @functools.lru_cache(maxsize=None)
    def dp(remaining):
        if remaining == 0:
            return 0  # no coins needed
        if remaining < 0:
            return float('inf')  # impossible
        # Try each coin and take the minimum
        return 1 + min(dp(remaining - c) for c in coins)

    result = dp(amount)
    return result if result != float('inf') else -1

print(coin_change_top_down([1, 5, 6, 9], 11))  # 2: (5+6) or (2*5+1?no: 9+2?no) 5+6=11 YES
print(coin_change_top_down([2], 3))             # -1: impossible
print(coin_change_top_down([1, 2, 5], 11))      # 3: 5+5+1

Escaliers descendants avec k marches

Généralisez le problème des escaliers pour autoriser de 1 à k marches. L'état correspond à la marche actuelle ; depuis la marche i, vous pouvez atteindre les marches i+1, i+2, ..., i+k. La récurrence est la suivante : dp(i) = sum of dp(i-j) for j in 1..k if i-j >= 0. La mémoïsation donne une complexité de O(n*k), au lieu de O(k^n). Cette généralisation apparaît dans des problèmes comme « coût minimal pour atteindre la dernière marche » et « nombre de façons de remplir une grille ».

import functools

def climb_k_steps(n, k):
    @functools.lru_cache(maxsize=None)
    def dp(i):
        if i == 0:
            return 1  # base: one way to stay at ground
        if i < 0:
            return 0  # impossible
        # From stair i, you could have come from i-1, i-2, ..., i-k
        return sum(dp(i - j) for j in range(1, k+1) if i - j >= 0)

    return dp(n)

# k=2 (original): should match fib-like sequence
print([climb_k_steps(n, 2) for n in range(7)])  # [1,1,2,3,5,8,13]
# k=3: more options
print([climb_k_steps(n, 3) for n in range(7)])  # [1,1,2,4,7,13,24]

LCS descendante : mémoïsation 2D

La plus longue sous-séquence commune (LCS) nécessite un état 2D : dp(i, j) = longueur de la LCS de s1[:i] et s2[:j]. Si s1[i-1] == s2[j-1], les caractères correspondent : dp(i,j) = 1 + dp(i-1, j-1). Sinon : dp(i,j) = max(dp(i-1,j), dp(i,j-1)) — ignorez un caractère de l'une ou l'autre chaîne. La mémoïsation sur (i, j) donne une complexité de O(mn), au lieu de O(2^(m+n)).

import functools

def lcs_top_down(s1, s2):
    m, n = len(s1), len(s2)

    @functools.lru_cache(maxsize=None)
    def dp(i, j):
        if i == 0 or j == 0:
            return 0  # empty prefix has LCS of 0
        if s1[i-1] == s2[j-1]:
            return 1 + dp(i-1, j-1)  # characters match
        return max(dp(i-1, j), dp(i, j-1))  # skip one

    return dp(m, n)

print(lcs_top_down('abcde', 'ace'))   # 3: 'ace'
print(lcs_top_down('abc', 'abc'))     # 3: 'abc'
print(lcs_top_down('abc', 'def'))     # 0: no common chars

Dictionnaire de mémoïsation ou lru_cache : lequel choisir

Utilisez @lru_cache lorsque les arguments de votre fonction sont des types primitifs hachables (int, str, tuple). Utilisez un dictionnaire de mémoïsation manuel lorsque vous devez transmettre un état mutable (listes, dictionnaires) en le convertissant en tuples, lorsque vous devez suivre les clés qui ont été calculées ou lorsque vous êtes dans une méthode de classe où self ne doit pas être mis en cache. Le dictionnaire de mémoïsation manuel est plus explicite et évite les problèmes subtils liés aux fermetures dans les fonctions auxiliaires récursives.

# @lru_cache: clean, automatic, O(1) overhead
# Use when: arguments are simple (int, str, tuple)
import functools
@functools.lru_cache(maxsize=None)
def simple_dp(n):
    if n <= 1: return n
    return simple_dp(n-1) + simple_dp(n-2)

# Manual memo dict: explicit, flexible
# Use when: complex state, need to inspect memo, class methods
def manual_memo_dp(s1, s2):
    memo = {}
    def dp(i, j):
        if (i,j) in memo: return memo[(i,j)]
        if i == 0 or j == 0:
            return 0
        if s1[i-1] == s2[j-1]:
            memo[(i,j)] = 1 + dp(i-1, j-1)
        else:
            memo[(i,j)] = max(dp(i-1,j), dp(i,j-1))
        return memo[(i,j)]
    return dp(len(s1), len(s2))

print(manual_memo_dp('abcde', 'ace'))  # 3

Somme cible descendante

Somme cible (LeetCode #494) : attribuez + ou - à chaque nombre et comptez les affectations qui produisent une somme cible. État : dp(index, current_sum). À chaque index, essayez d'additionner (+) et de soustraire (-) le nombre courant. La mémoïsation sur (index, current_sum) transforme la force brute en O(2^n) en une solution en O(n * sum_range). L'intervalle des sommes est borné par la somme totale de tous les nombres, ce qui donne O(n * S) états au total.

import functools

def find_target_sum_ways(nums, target):
    @functools.lru_cache(maxsize=None)
    def dp(index, current_sum):
        if index == len(nums):
            return 1 if current_sum == target else 0
        # Try adding the number
        add = dp(index + 1, current_sum + nums[index])
        # Try subtracting the number
        subtract = dp(index + 1, current_sum - nums[index])
        return add + subtract

    return dp(0, 0)

print(find_target_sum_ways([1,1,1,1,1], 3))  # 5
print(find_target_sum_ways([1], 1))            # 1
print(find_target_sum_ways([1], -1))           # 1

DP descendante ou ascendante : avantages et inconvénients

DP descendante (mémoïsation) — avantages : naturelle à écrire (elle part de la solution récursive), elle ne calcule que les sous-problèmes réellement nécessaires (évaluation paresseuse) et il est facile d'y ajouter progressivement un cache. DP ascendante (tabulation) — avantages : aucun surcoût lié à la pile d'appels (pas de limite de récursion Python), accès mémoire favorisant le cache et optimisation de l'espace mémoire plus facile. Les deux approches ont la même complexité asymptotique. Lors des entretiens, commencez par la DP descendante pour vérifier la correction, puis convertissez-la en DP ascendante si l'on vous demande une meilleure utilisation de l'espace mémoire.

# Top-down advantages:
# + Natural: write recursive, add @cache
# + Lazy: only computes needed sub-problems
# + Easy to reason about correctness
# - Uses call stack (recursion limit in Python)
# - Higher constant factor (function call overhead)

# Bottom-up advantages:
# + No recursion limit
# + Better cache performance (sequential memory)
# + Easier to space-optimise (rolling array)
# - Must compute all sub-problems in order
# - Less intuitive for complex 2D/3D problems

# Interview strategy:
# Start with top-down to verify recurrence,
# convert to bottom-up only if asked.
print('Top-down: easy to write | Bottom-up: efficient for large n')

Segmentation de mots avec une DP descendante

Segmentation de mots (LeetCode #139) consiste à déterminer si une chaîne s peut être segmentée en mots provenant d'un dictionnaire. État : dp(i) = indique si s[i:] peut être segmentée. Depuis l'index i, essayez tous les mots : si s[i:i+len(w)] == w, appelez récursivement la fonction sur le suffixe restant. La mémoïsation sur l'index de départ transforme la force brute en O(2^n) en une solution en O(n^2) (ou O(n * max_word_len)) grâce à la vérification d'appartenance à l'ensemble.

import functools

def word_break(s, word_dict):
    word_set = set(word_dict)

    @functools.lru_cache(maxsize=None)
    def dp(start):
        if start == len(s):
            return True  # successfully segmented entire string
        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set and dp(end):
                return True
        return False

    return dp(0)

print(word_break('leetcode', ['leet', 'code']))       # True
print(word_break('applepenapple', ['apple', 'pen'])) # True
print(word_break('catsandog', ['cats', 'dog', 'and', 'cat', 'san', 'andog'])) # False

Limite de récursion et itertools

La limite de récursion par défaut de Python est de 1000 (définie par sys.getrecursionlimit()). Pour les problèmes de DP portant sur de grandes entrées (n = 10 000 ou plus), la mémoïsation descendante atteindra cette limite. Vous pouvez augmenter la limite avec sys.setrecursionlimit(100000) ou convertir la solution en DP ascendante. En programmation compétitive, augmenter la limite est courant ; dans le code de production, préférez toujours une solution ascendante ou itérative pour plus de fiabilité.

import sys

print('Default recursion limit:', sys.getrecursionlimit())  # 1000

# For large DP problems, increase if needed:
# sys.setrecursionlimit(100000)

# Better: convert to bottom-up DP for large n
def fib_bottom_up(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a + b
    return b

# No recursion limit issue:
print(fib_bottom_up(10000))  # works fine, no recursion

Vérification rapide

Vérifiez 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.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris : la DP descendante avec un dictionnaire de mémoïsation et le décorateur @lru_cache, des solutions avec mémoïsation pour Fibonacci, le rendu de monnaie, la LCS, la somme cible et la segmentation de mots, ainsi que les situations où choisir une approche descendante plutôt qu'ascendante. Ensuite, nous implémenterons la DP ascendante avec tabulation et optimisation de l'espace mémoire.

Questions Fréquemment Posées

La leçon « DP descendante avec mémoïsation » est-elle gratuite ?

Oui — le texte complet de « DP descendante avec mémoïsation » 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 DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « DP descendante avec mémoïsation » ?

Ajoutez un dictionnaire de mémoïsation à une solution récursive pour éliminer les appels en double, et utilisez @lru_cache avec un minimum de code. Tu pratiques DSA 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 DSA Interview Prep ?

Aucune expérience préalable n'est requise. DSA 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 2 sur 4.

Combien de temps prend la leçon « DP descendante avec mémoïsation » ?

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 DSA Interview Prep ?

Oui. Chaque leçon DSA 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

  1. Reconnaître la DP : sous-problèmes qui se recouvrent
  2. DP descendante avec mémoïsation
  3. DP ascendante avec tabulation
  4. Rendu de monnaie et escalier au coût minimal
← Retour à DSA Interview Prep