Learn
Dynamic Programming: Memoization
Dynamic Programming (DP) is an optimization technique that solves complex problems by breaking them into overlapping subproblems and storing results to avoid redundant computation. DP is also known as "memoization" when applied top-down.
You have two approaches. With top-down memoization, you add a cache to your recursion. With bottom-up tabulation, you build answers iteratively from base cases.
Top-down with memoization:
memo = {}
function fib(n):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
Bottom-up tabulation:
function fib(n):
if n <= 1:
return n
dp = array of size n + 1
dp[0] = 0
dp[1] = 1
for i from 2 to n:
dp[i] = (dp[i-1] + dp[i-2]) mod (10^9 + 7)
return dp[n]
You transform into by eliminating redundant calculations.