Solving a Question with DP
EasyState → recurrence → base case → order → answer
Find how a problem depends on smaller versions of itself, then fill a table from small to big.
The idea
A repeatable process: name the subproblem (state), express it via smaller states (recurrence), pin the smallest cases (base), fill in dependency order, and read off the answer.
0
0
0
0
0
0
0
0
1
2
3
4
5
6
Step 1 of 8. The recipe: define state, write the recurrence, set base cases, fill in order, read the answer. Values: 0, 0, 0, 0, 0, 0, 0.
1/8
Optimal
timevariesspacevaries
The five questions to ask.
1function solve(input) {2 const dp = new Array(n + 1);3 dp[0] = base;4 for (let i = 1; i <= n; i++)5 dp[i] = combine(dp[i - 1], /* ... */);6 return dp[n];7}Input
- array
- [0, 0, 0, 0, 0, 0, 0]
Memory
- dp[1]
- —
- dp[2]
- —
- dp[3]
- —
- dp[4]
- —
- dp[5]
- —
- dp[6]
- —
Output
- dp[6]
- —
Check yourself
2 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 2
- Output:
- 2
- Explanation:
- Two ways: 1+1 or a single 2-step.
Example 2
- Input:
- n = 3
- Output:
- 3
- Explanation:
- 1+1+1, 1+2, or 2+1 → 3 ways.
Example 3
- Input:
- n = 5
- Output:
- 8
- Explanation:
- The count follows Fibonacci → 8.
Finished the walkthrough? Add it to your streak.