Solving a Question with DP
A systematic 5-step framework for solving any Dynamic Programming problem.
Examples
Start on step 1, pay 15, and stride straight past the top. Step 2 is never used.
Start on step 0 and take a two-step stride over each 100. Six cheap steps are paid for.
The loop body never runs past its base cases: the cheaper of the two starting steps is the whole answer.
The Framework
Solving DP problems can be daunting. Use this 5-step framework to break it down systematically.
Step 1: Define the Objective
What are we minimizing, maximizing, or counting?
- Example: "Find the minimum cost to climb stairs."
Step 2: Identify the State
What variables uniquely define our progress? Minimize the number of state variables.
- Example:
i= current stair index. - State:
dp[i]
Step 3: Recurrence Relation (Transitions)
How do we move from one state to another? This is the core equation.
- Example:
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
Step 4: Base Cases
When does the recursion stop? What are the trivial answers?
- Example:
dp[0] = cost[0],dp[1] = cost[1]
Step 5: Implementation (Memo vs Tabulation)
Decide whether to write it top-down (recursion plus a memo) or bottom-up (a loop plus a table).
- Top-down: closer to the recurrence you just wrote, and it only ever visits states it needs.
- Bottom-up: no call stack to overflow, and it opens the door to keeping only the last row or two.
The walkthrough below is the bottom-up version of the five steps above.
Interactive Walkthrough (Min Cost Climbing Stairs)
ROW cost = WHAT A STEP CHARGES · ROW dp = CHEAPEST TOTAL TO STAND THERE · OUTLINED = THE TWO CELLS IT IS BUILT FROM
NEXT STEP OF THE STAIRCASE
0
1
2
cost
dp
steps
3
filled
0/3
Answer
—
the five steps
1. OBJECTIVE — LEAST TOTAL COST TO GET PAST THE TOP
2. STATE — dp[i], CHEAPEST TOTAL TO STAND ON STEP i
3. TRANSITION — dp[i] = cost[i] + min(dp[i−1], dp[i−2])
4. BASE — dp[0] = cost[0], dp[1] = cost[1]
5. ANSWER — min(dp[n−1], dp[n−2])
Take step 0, which charges 10
Next
You may start on step 0 or step 1, so step 0 costs only itself: dp[0] = 10
cost
Legend & Complexity
The cell being written
The two cells it is built from
A dash: not computed yet
Time
O(n)
Space
O(n)
Space, rolled
O(1)
Row cost is what each step charges; row dp is the cheapest total to be standing on it. Watch the two outlined cells feed the one being written — that is step 3, the transition, doing its work.
Try Skip last: dp[2] is not the answer, and the last frame shows why.
Example: Climbing Stairs
The five steps, written out. The base cases sit inside the loop so every step of the staircase is handled the same way.
Solving a Question with DP Code
1var minCostClimbingStairs = function(cost) {2 const n = cost.length;3 const dp = new Array(n).fill(0);45 for (let i = 0; i < n; i++) {6 if (i < 2) {7 dp[i] = cost[i];8 continue;9 }10 const best = Math.min(dp[i - 1], dp[i - 2]);11 dp[i] = cost[i] + best;12 }1314 return Math.min(dp[n - 1], dp[n - 2]);15};