Overview
Dynamic programming applies when a problem breaks into overlapping subproblems — the same smaller question is asked again and again — and the best answer can be built from best answers to those subproblems. Instead of recomputing, you store each answer once. Climbing stairs, house robber and coin change are the classic first examples.
Every DP solution has the same four parts: a state (what dp[i] means, in words), a recurrence (how dp[i] is computed from smaller states), base cases, and an evaluation order. You can write it top-down as recursion with memoisation, or bottom-up as a loop filling a table. If dp[i] only depends on the last few values, you can keep just those and use O(1) space.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| General | O(number of states × work per state) |
| Climbing stairs / house robber | O(n) time, O(1) space |
| Coin change | O(amount × coins) |
| LIS | O(n²) or O(n log n) |
Patterns to recognise
Fibonacci-style
Use it for: Climbing stairs, house robber, decode ways.
dp[i] combines dp[i − 1] and dp[i − 2] depending on the choice at step i.
Unbounded choices
Use it for: Coin change, word break, perfect squares.
For each target value, try every option that fits and take the best.
Best ending here
Use it for: Longest increasing subsequence, maximum product subarray.
dp[i] = best answer for sequences ending exactly at index i.
Code template
def rob(nums):
take = skip = 0 # best if we rob / skip the previous house
for x in nums:
take, skip = skip + x, max(take, skip)
return max(take, skip)
def coin_change(coins, amount):
INF = amount + 1
dp = [0] + [INF] * amount # dp[a] = fewest coins to make a
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] <= amount else -1
int rob(const vector<int>& nums) {
int take = 0, skip = 0; // best if we rob / skip the previous house
for (int x : nums) {
int newTake = skip + x;
skip = max(take, skip);
take = newTake;
}
return max(take, skip);
}
int coinChange(const vector<int>& coins, int amount) {
const int INF = amount + 1;
vector<int> dp(amount + 1, INF); // dp[a] = fewest coins to make a
dp[0] = 0;
for (int a = 1; a <= amount; ++a)
for (int c : coins)
if (c <= a) dp[a] = min(dp[a], dp[a - c] + 1);
return dp[amount] <= amount ? dp[amount] : -1;
}
Common mistakes
- Starting to code before writing down what the state means.
- Wrong base cases — dp[0] for "make amount 0" is 0 coins, not infinity.
- Using INT_MAX as infinity and then adding 1 overflows.
- Filling the table in an order where dp[i] is read before it is computed.
Quick check
Three questions on DP 1D. Get all three right to earn +15 XP.
-
Dynamic programming applies when a problem has:
The same subproblems recur, and their best answers combine into the overall best answer.
-
Climbing stairs with 1 or 2 steps at a time: which recurrence counts the ways to reach step i?
The last move came from step i - 1 or step i - 2.
-
When dp[i] depends only on dp[i-1] and dp[i-2], the memory can be reduced from O(n) to:
Keep just the last two values in variables.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Climbing StairsLeetCode Easy +20
- Min Cost Climbing StairsLeetCode Easy +20
- House RobberLeetCode Medium +40
- House Robber IILeetCode Medium +40
- Coin ChangeLeetCode Medium +40
- Decode WaysLeetCode Medium +40
- Word BreakLeetCode Medium +40
- Longest Increasing SubsequenceLeetCode Medium +40
- Longest Valid ParenthesesLeetCode Hard +70
Stuck on DP 1D?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor