ƒ(x) PatternsAdvanced interactive
Dynamic Programming
Solve once, remember, reuse. Overlapping subproblems.
fibonacci_tabulation
step 1 / 21
0
dp[0]·
dp[1]·
dp[2]·
dp[3]·
dp[4]·
dp[5]·
dp[6]·
dp[7]·
dp[8]·
dp[9]·
dp[10]Base case: dp[0] = 0.
dependenciesjust computeddp[i] = dp[i-1] + dp[i-2]
speed1×
How it works
Dynamic programming breaks a problem into overlapping subproblems and stores each answer so it's computed only once — via top-down memoization or bottom-up tabulation. It collapses exponential recursion into polynomial time.
Mental models
- Two ingredients: optimal substructure + overlapping subproblems.
- Memoization caches recursion; tabulation fills a table iteratively.
Complexity
- Time
- O(states × work)
- Space
- O(states)often reducible
Reach for it when
- Knapsack
- Edit distance
- Longest common subsequence