Every DP solution comes from the same five decisions. Make them explicitly — on paper, or out loud in an interview — and the code almost writes itself. This lesson walks through the recipe on one example, then maps it onto the five patterns of this course.
dp[i] = the fewest steps to get from i down to 1." Most mistakes come from a vague state.i you can step to i − 1, to i / 2 if i is even, or to i / 3 if divisible by 3. So dp[i] = 1 + min of whichever of those are allowed.dp[1] = 0.dp[i] reads smaller indexes, so i = 2, 3, …, n.dp[n].Then check the cost: states × work per state = n × O(1) = O(n) time, O(n) space.
1. Plain recursion — the recurrence written directly. Exponential: minSteps(10) and minSteps(9) both ask about 3, 4, 5, …
function minSteps(n) { if (n === 1) return 0; // base case let best = minSteps(n - 1); // subtract 1 if (n % 2 === 0) best = Math.min(best, minSteps(n / 2)); // divide by 2 if (n % 3 === 0) best = Math.min(best, minSteps(n / 3)); // divide by 3 return 1 + best;}2. Memoization — cache minSteps(i): O(n) time, but n recursion levels deep (a stack overflow for n = 100,000).
function minSteps(n, memo = new Map()) { if (n === 1) return 0; if (memo.has(n)) return memo.get(n); let best = minSteps(n - 1, memo); if (n % 2 === 0) best = Math.min(best, minSteps(n / 2, memo)); if (n % 3 === 0) best = Math.min(best, minSteps(n / 3, memo)); memo.set(n, 1 + best); return 1 + best;}3. Tabulation — the table, filled from 2 up to n:
Each dp[i] picks the best of its allowed moves, reading cells that are already filled.
function minSteps(n) { const dp = new Array(n + 1).fill(0); // dp[i]: fewest steps from i down to 1 for (let i = 2; i <= n; i++) { dp[i] = dp[i - 1] + 1; // subtract 1 if (i % 2 === 0) dp[i] = Math.min(dp[i], dp[i / 2] + 1); // or divide by 2 if (i % 3 === 0) dp[i] = Math.min(dp[i], dp[i / 3] + 1); // or divide by 3 } return dp[n];}
Why not just divide whenever you can? Greedy fails: for 10, dividing by 2 gives 10 → 5 → 4 → 2 → 1 (4 steps), but 10 → 9 → 3 → 1 takes 3. DP tries every choice and keeps the best — that's what makes it correct where greedy isn't.
Most interview DP problems use one of five state shapes. Recognising the shape tells you the state, and the state tells you almost everything else:
pattern state typical recurrence
1D DP dp[i]: answer for a prefix from dp[i-1], dp[i-2] Climbing Stairs, House Robber, Decode Ways
Grid DP dp[r][c]: answer at a cell from the cell above / left Unique Paths, Minimum Path Sum
Knapsack dp[c]: answer for capacity c take or skip each item Partition Subset Sum, Coin Change
Sequences and strings dp[i][j]: two prefixes match, skip one, or edit LCS, Edit Distance, LIS, Word Break
State machines, intervals dp[i][state] or dp[l][r] moves between states / splits Stock with Cooldown, Burst Balloons