53. Exemple DP 1 : Memoization (Approche Top-Down)

La Memoization est une technique de programmation dynamique descendante (top-down) où nous utilisons la récursivité combinée à une table de consultation (souvent un Hash Map ou un tableau) pour stocker les résultats des appels de fonction coûteux et renvoyer le résultat mis en cache lorsque les mêmes entrées se reproduisent.

Exemple de Séquence de Fibonacci (Memoized)

Le calcul récursif standard de Fibonacci est exponentiel O(2^N) car il recalcule les résultats de manière extensive.

python memo = {} def fib_memo(n): if n <= 1: return n if n in memo: return memo[n] # Returning cached result

result = fib_memo(n - 1) + fib_memo(n - 2)
memo[n] = result # Store the result
return result

En ajoutant la memoization, la complexité temporelle chute drastiquement à O(N), car chaque nombre de 1 à N est calculé exactement une fois.