Fundamentals
EasyOverlapping subproblems · a table you fill once
Break a problem into smaller ones, solve each once, and remember the answers so you never redo work.
The idea
DP applies when a big problem breaks into smaller versions of itself that repeat. Instead of recomputing them, store each answer in a table and build up from base cases.
The trick
- Optimal substructure: the best answer is built from best answers to subproblems.
- Memoization is top-down; tabulation is bottom-up. Same idea, different direction.
0
1
0
0
0
0
0
0
0
1
2
3
4
5
6
7
Step 1 of 8. Overlapping subproblems: fill a table once instead of recomputing. Fibonacci is the classic. Values: 0, 1, 0, 0, 0, 0, 0, 0.
1/8
Optimal
timevariesspacevaries
State → recurrence → base → order.
1// 1. Define state: dp[i] means ...2// 2. Recurrence: dp[i] = f(dp[i-1], dp[i-2], ...)3// 3. Base cases: dp[0], dp[1] = ...4// 4. Evaluation order: fill so deps come first5// 5. Answer: dp[n]Input
- array
- [0, 1, 0, 0, 0, 0, 0, 0]
Memory
- dp[2]
- —
- dp[3]
- —
- dp[4]
- —
- dp[5]
- —
- dp[6]
- —
- dp[7]
- —
Output
- dp[7]
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- fib(5) with memoisation
- Output:
- 5, after 9 calls instead of 15
- Explanation:
- fib(3) is computed once and read back the second time. The recursion tree collapses into a line.
Example 2
- Input:
- the same, bottom-up
- Output:
- dp = [0,1,1,2,3,5]
- Explanation:
- State is 'the i-th number', the recurrence is dp[i] = dp[i-1] + dp[i-2], the base cases are dp[0] and dp[1], and the order is left to right. That is the whole recipe.
Finished the walkthrough? Add it to your streak.