Solving a Question with Dynamic Programming
MediumState, recurrence, base case, order
Problem
Learn the DP recipe: define the state, write the recurrence, add base cases, then memoize or tabulate.
Describe the subproblem, how it builds from smaller ones, and store answers to reuse.
The idea
Dynamic programming is recursion with the repeated work removed. Name the state — the smallest set of facts that determines the answer from here — write the recurrence between states, fix the base cases, then either memoise the recursion or fill a table in an order where every dependency is already computed.
The trick
- If two different paths reach the same state, DP applies.
- Top-down memoisation and bottom-up tabulation compute the same thing; tabulation avoids the stack.
- Once the recurrence only looks back a fixed distance, you can drop the table to a few variables.
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.
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
1 quick question about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- fib(n)
- Output:
- top-down or bottom-up
Finished the walkthrough? Add it to your streak.