DP in one paragraph
DP is remembering answers to subproblems. You only need it when (1) the naive recursion repeats work and (2) subproblems overlap. Interview move: define dp[...] in words first (‘best money from houses i…n’), then the formula, then code.
Analogy: sticky-note homework
DP is doing homework with sticky notes: when you solve a subproblem, you stick the answer on the fridge. Next time you need it, you read the note instead of redoing the algebra. If subproblems don’t overlap, sticky notes don’t help — that’s plain recursion / divide-and-conquer.
Worked example: house robber
Cannot rob adjacent houses. Let dp[i] = best from index i to end. Transition: max(rob i + dp[i+2], skip i → dp[i+1]). Base: empty = 0.
def rob(nums):
# bottom-up rolling
take = skip = 0
for x in nums:
take, skip = skip + x, max(skip, take)
return max(take, skip)
# nums=[2,7,9,3,1]
# walk: after each house update take/skip — final max=12 (2+9+1)int rob(int[] nums) {
// bottom-up rolling
int take = 0, skip = 0;
for (int x : nums) {
int newTake = skip + x;
skip = Math.max(skip, take);
take = newTake;
}
return Math.max(take, skip);
}
// nums=[2,7,9,3,1]
// walk: after each house update take/skip — final max=12 (2+9+1)0/1 knapsack sketch
def knapsack(weights, values, W):
dp = [0] * (W + 1)
for w, v in zip(weights, values):
for cap in range(W, w - 1, -1): # backward so each item once
dp[cap] = max(dp[cap], dp[cap - w] + v)
return dp[W]int knapsack(int[] weights, int[] values, int W) {
int[] dp = new int[W + 1];
for (int i = 0; i < weights.length; i++) {
int w = weights[i], v = values[i];
for (int cap = W; cap >= w; cap--) { // backward so each item once
dp[cap] = Math.max(dp[cap], dp[cap - w] + v);
}
}
return dp[W];
}What a good explanation sounds like
You: ‘State is the best we can do starting at house i. From i I either rob it and skip to i+2, or skip to i+1. I’ll compute bottom-up so I don’t blow the stack and I can roll two variables.’
When to reach for this pattern
Interview order: define state in words, write the transition, fix base cases, then code. Jumping to a 2D array without the sentence is how people get lost.
Core template + worked trace
House robber — rolling two variables after stating state:
def rob(nums: list[int]) -> int:
# take = best ending by robbing current; skip = best ending by skipping
take = skip = 0
for x in nums:
take, skip = skip + x, max(skip, take)
return max(take, skip)
# nums=[2,7,9,3,1]
# x=2: take=2 skip=0
# x=7: take=0+7=7 skip=max(0,2)=2
# x=9: take=2+9=11 skip=max(2,7)=7
# x=3: take=7+3=10 skip=max(7,11)=11
# x=1: take=11+1=12 skip=max(11,10)=11 → answer 12int rob(int[] nums) {
// take = best ending by robbing current; skip = best ending by skipping
int take = 0, skip = 0;
for (int x : nums) {
int newTake = skip + x;
skip = Math.max(skip, take);
take = newTake;
}
return Math.max(take, skip);
}
// nums=[2,7,9,3,1]
// x=2: take=2 skip=0
// x=7: take=0+7=7 skip=max(0,2)=2
// x=9: take=2+9=11 skip=max(2,7)=7
// x=3: take=7+3=10 skip=max(7,11)=11
// x=1: take=11+1=12 skip=max(11,10)=11 → answer 120/1 knapsack — backward capacity loop:
def knapsack(weights, values, W):
dp = [0] * (W + 1)
for w, v in zip(weights, values):
for cap in range(W, w - 1, -1): # backward ⇒ each item once
dp[cap] = max(dp[cap], dp[cap - w] + v)
return dp[W]
# weights=[2,3,4], values=[3,4,5], W=5
# after item2: can take 2→3 or 3→4; after item4: 2+3=5 → value 3+4=7int knapsack(int[] weights, int[] values, int W) {
int[] dp = new int[W + 1];
for (int i = 0; i < weights.length; i++) {
int w = weights[i], v = values[i];
for (int cap = W; cap >= w; cap--) { // backward ⇒ each item once
dp[cap] = Math.max(dp[cap], dp[cap - w] + v);
}
}
return dp[W];
}
// weights=[2,3,4], values=[3,4,5], W=5
// after item2: can take 2→3 or 3→4; after item4: 2+3=5 → value 3+4=7Edge cases & common bugs
Complexity — say it aloud
Interview talk track
You: ‘State is the best we can do starting at house i. From i I either rob it and jump to i+2, or skip to i+1. I’ll compute bottom-up and roll two variables so space is O(1).’
Practice set
- Climbing Stairs
- House Robber / House Robber II
- Coin Change
- Longest Increasing Subsequence
- Unique Paths
- 0/1 Knapsack / Target Sum
- Edit Distance
- Longest Common Subsequence
Harder follow-up
Harder variant: Edit Distance — dp[i][j] = min ops to turn a[:i] into b[:j]. Transition: delete / insert / replace. Trace a 3×3 corner on the board before filling the table.
Pattern bank: more questions + efficient solutions
Five DP staples. Say state → transition → base out loud before writing loops.
Q: Climbing Stairs: you can climb 1 or 2 steps. How many distinct ways to reach the top of n stairs? (Fibonacci-style recurrence.)
# Climbing Stairs — O(n) time, O(1) space
def climb_stairs(n: int) -> int:
if n <= 2:
return n
a, b = 1, 2
for _ in range(3, n + 1):
a, b = b, a + b
return b// Climbing Stairs — O(n) time, O(1) space
int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2;
for (int i = 3; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}Q: Coin Change (unbounded): given coin denominations and amount, return the fewest coins needed to make that amount, or −1 if impossible.
# Coin Change unbounded — O(amount * coins)
def coin_change(coins, amount: int) -> int:
INF = amount + 1
dp = [INF] * (amount + 1)
dp[0] = 0
for x in range(1, amount + 1):
for c in coins:
if c <= x:
dp[x] = min(dp[x], dp[x - c] + 1)
return dp[amount] if dp[amount] < INF else -1// Coin Change unbounded — O(amount * coins)
int coinChange(int[] coins, int amount) {
int INF = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, INF);
dp[0] = 0;
for (int x = 1; x <= amount; x++)
for (int c : coins)
if (c <= x) dp[x] = Math.min(dp[x], dp[x - c] + 1);
return dp[amount] >= INF ? -1 : dp[amount];
}Q: Longest Increasing Subsequence: length of the longest strictly increasing subsequence in an integer array.
# LIS — clear O(n^2); note: O(n log n) via patience sorting / bisect tails
def length_of_lis(nums) -> int:
n = len(nums)
if n == 0:
return 0
dp = [1] * n
best = 1
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
best = max(best, dp[i])
return best
# O(n log n) sketch: maintain tails[len] = smallest tail of all LIS of that length; bisect_left// LIS — O(n^2); O(n log n) via patience sorting for follow-up
int lengthOfLIS(int[] nums) {
int n = nums.length, best = 1;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++)
if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
best = Math.max(best, dp[i]);
}
return n == 0 ? 0 : best;
}Q: Edit Distance: minimum operations (insert, delete, replace) to convert word1 into word2.
# Edit Distance — O(mn)
def min_distance(word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[m][n]// Edit Distance — O(mn)
int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (word1.charAt(i - 1) == word2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1];
else
dp[i][j] = 1 + Math.min(dp[i - 1][j],
Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
return dp[m][n];
}Q: House Robber II: houses in a circle (first and last adjacent). Return max money without robbing two adjacent houses. (Alternate: Unique Paths on an m×n grid — included below as comment twin.)
# House Robber II — O(n) time, O(1) space
def rob(nums) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
def rob_linear(lo, hi):
prev2 = prev1 = 0
for i in range(lo, hi + 1):
prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
return prev1
n = len(nums)
return max(rob_linear(0, n - 2), rob_linear(1, n - 1))
# Unique Paths twin: dp[j] += dp[j-1] across rows — O(mn) time, O(n) space// House Robber II — O(n) time, O(1) space
int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
return Math.max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
}
int robLinear(int[] nums, int lo, int hi) {
int prev2 = 0, prev1 = 0;
for (int i = lo; i <= hi; i++) {
int cur = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}