Advanced · Module 18 · Lesson 1
DP thinking
State, transition, base case, answer, and computation order.
Lesson 105 of 123
1d streakInteractive Visualization
Trace the algorithm state by state
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive algorithm lab
0/1 Knapsack DP Table
Build reusable states from smaller capacities
Item row
0
Capacity
0
Choice
base
Best value
0
| items \ cap | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | · | · | · | · | · | · |
| 2 | · | · | · | · | · | · |
| 3 | · | · | · | · | · | · |
Why this step happens
With zero items or zero capacity, the best value is 0.
dp[i][c] stores the best value using the first i items within capacity c.
Theory lesson · Step-by-step
Understand DP thinking
State, transition, base case, answer, and computation order.
Worked approach
Trace the reasoning step by step
- 1Define the minimal state variables needed by DP thinking.
- 2Write the recurrence as choices from smaller states.
- 3Set base cases for the smallest reachable states.
- 4Choose memoization or an evaluation order in which dependencies are ready.
- 5Return the requested state, then optimize memory only if dependency order permits.
Concrete example
Count ways to climb 4 stairs using steps 1 or 2.
- 1dp[0]=1, dp[1]=1.
- 2dp[i]=dp[i−1]+dp[i−2].
dp[4]=5 ways.
What must remain true (Loop Invariant)
Every state consumed by DP thinking already stores the correct answer for its declared subproblem, so each transition uses only valid dependencies.
Cost Model
Complexity & Trade-offs
When to use it
- Optimization, counting, and feasibility with overlapping subproblems.
- Sequence, grid, interval, tree, subset, and digit constraints.
- Replacing exponential recursion with reusable state.
Common mistakes
- Defining a state that lacks information needed by the transition.
- Iterating in an order that reads unresolved or same-round values.
- Optimizing space before proving dependencies.
Practice prompts
- Reproduce the worked DP thinking example without looking at the trace.
- Change one input condition and explain whether the DP thinking invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check