53. DP Example 1: Memoization (Top-Down Approach)

Memoization is a top-down dynamic programming technique where we use recursion combined with a lookup table (often a Hash Map or array) to store the results of expensive function calls and return the cached result when the same inputs occur again.

Fibonacci Sequence Example (Memoized)

The standard recursive Fibonacci calculation is exponential O(2^N) because it recomputes results extensively.

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

By adding memoization, the time complexity drops drastically to O(N), as each number from 1 to N is computed exactly once.