Basic DP Questions
Six warm-ups to lock in the state-design checklist. Every one of these is 1D linear DP with one or two predecessors. They’re the muscle-memory exercises before the heavier patterns.
For each problem, try writing the state, transition, and base cases yourself before peeking. That’s where the learning is.
1. Fibonacci with memoization
Compute the n-th Fibonacci number where fib(0) = 0, fib(1) = 1.
State: dp[i] = fib(i). Transition: dp[i] = dp[i - 1] + dp[i - 2]. Base: dp[0] = 0, dp[1] = 1.
Time: O(n). Space: O(1).
2. Climbing Stairs
You can climb 1 or 2 stairs at a time. How many ways to climb n stairs?
The recurrence is literally Fibonacci. To reach step i, the last move was a 1-step (from i - 1) or a 2-step (from i - 2).
Time: O(n). Space: O(1).
3. Min Cost Climbing Stairs
cost[i] is the cost of stepping on stair i. You can start at stair 0 or 1 and climb 1 or 2 stairs at a time. Find the minimum cost to reach the top (past the last stair).
State: dp[i] = min cost to reach and step on stair i. Transition: dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]). Answer: min(dp[n - 1], dp[n - 2]) — you can jump off either of the top two.
Time: O(n). Space: O(1).
4. House Robber
Can’t rob two adjacent houses. Maximize total loot.
State: dp[i] = best loot considering the first i + 1 houses. Transition: at house i, skip it (dp[i - 1]) or take it (nums[i] + dp[i - 2]).
Time: O(n). Space: O(1).
5. Maximum Subarray (Kadane)
Find the contiguous sub-array with the largest sum.
State: dp[i] = best sum of a sub-array ending at i. Transition: dp[i] = max(nums[i], nums[i] + dp[i - 1]) — either start fresh or extend.
Time: O(n). Space: O(1).
Kadane’s algorithm is the cleanest piece of DP you’ll ever write. The recurrence — “either start fresh or extend” — captures the entire idea of contiguous-subarray problems in two operands.
6. Unique Paths
Count paths in an m × n grid from top-left to bottom-right, moving only right or down.
State: dp[i][j] = paths to cell (i, j). Transition: dp[i][j] = dp[i - 1][j] + dp[i][j - 1].
Space-optimized to one row:
dp[j] (after update) plays the role of dp[i][j]; dp[j] (before update) plays the role of dp[i - 1][j]; dp[j - 1] is dp[i][j - 1] (already updated this row). One line of arithmetic = the full 2D recurrence.
Time: O(m × n). Space: O(n).
Mini-quiz
Next: the ten practice problems — one per pattern, with full state-design walkthroughs.