Step 3 · DSA
The two questions
😱
Riya has done 180 problems. She opens one marked "DP", reads it twice, and closes the tab. It is not that she cannot code. She does not know what to call dp, so there is nothing to type.
Dynamic programming is one idea: solve a small version, write the answer down, and reuse it instead of computing it again. The hard part is never the code. It is naming the small version. Two questions do that, and they are the same two questions every single time.
Question 1What is the state? Finish this sentence: "dp[i] is the best answer for ..." If the sentence needs two blanks, the state is two-dimensional: dp[i][j].
Question 2What choice do I make at this state? Usually two or three options. Take it or skip it. Use coin c or not. Characters match or they do not. The recurrence is just best of those choices.
Answer both and the code writes itself: make an array the size of the state, fill in the smallest cases by hand, loop in an order where everything you look back at is already filled, and return the last cell.
1Look back a fixed distanceFibonacci · climbing stairs
2Take it or skip itHouse robber
3Unlimited choices, minimiseCoin change
4Take or skip, with a capacity0/1 knapsack
5Two sequences, one tableLongest common subsequence
6Look back at every earlier stateLongest increasing subsequence
Shape 1 · asked as "Climbing Stairs"
Look back a fixed distance
You climb a staircase of n steps, taking 1 or 2 steps at a time. How many different ways are there to reach the top? Every state depends on a fixed, small number of states just behind it, so one array and one loop finish the job.
Statedp[i] = the number of ways to reach step i.
Choicethe last move was a 1-step or a 2-step.
Recurrenceways to reach i = ways to reach i-1, then step once + ways to reach i-2, then step twice. So dp[i] = dp[i-1] + dp[i-2], with dp[0] = dp[1] = 1.
def climb_stairs(n): # n >= 1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# climb_stairs(5) -> 8 dp = [1, 1, 2, 3, 5, 8]
int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
Same shape, different words: Fibonacci, tribonacci, "how many ways to decode this string", "min cost climbing stairs".
Shape 2 · asked as "House Robber"
Take it or skip it
Houses in a row, each with some money. You cannot rob two houses next to each other. What is the most you can take? At every house you have exactly two options, and you keep the better one.
Statedp[i] = the most money from the first i houses.
Choicerob house i (then house i-1 is out), or skip it.
Recurrencebest of the two: skip = dp[i-1], rob = dp[i-2] + nums[i-1]. So dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]), with dp[0] = 0 and dp[1] = nums[0].
def rob(nums):
n = len(nums)
dp = [0] * (n + 1) # dp[i] uses the first i houses
dp[1] = nums[0]
for i in range(2, n + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
return dp[n]
# rob([2, 7, 9, 3, 1]) -> 12 dp = [0, 2, 7, 11, 11, 12]
int rob(int[] nums) {
int n = nums.length;
int[] dp = new int[n + 1];
dp[1] = nums[0];
for (int i = 2; i <= n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[n];
}
The 12 is 2 + 9 + 1. The other alternating choice, 7 + 3, gives only 10. Which set of houses wins is not obvious by eye, so you let the table decide.
Shape 3 · asked as "Coin Change"
Unlimited choices, minimise
Coins of given values, unlimited supply of each. What is the fewest coins that make an amount? At every amount you may use any coin, so the inner loop is over the coins, not over "take or skip".
Statedp[a] = the fewest coins that make amount a.
Choicewhich coin to use last: any coin c with c <= a.
Recurrencedp[a] = 1 + min(dp[a - c]) over every coin c that fits. Base: dp[0] = 0. Unreachable amounts keep the INF marker and become -1.
def coin_change(coins, amount):
INF = amount + 1 # bigger than any real answer
dp = [INF] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1
return -1 if dp[amount] == INF else dp[amount]
# coin_change([1, 2, 5], 11) -> 3 (5 + 5 + 1)
# coin_change([2], 3) -> -1
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 a = 1; a <= amount; a++) {
for (int c : coins) {
if (c <= a && dp[a - c] + 1 < dp[a]) dp[a] = dp[a - c] + 1;
}
}
return dp[amount] == INF ? -1 : dp[amount];
}
Shape 4 · asked as "0/1 Knapsack"
Take or skip, with a capacity
Items with a weight and a value, a bag that holds a fixed weight, each item usable once. Maximise the value inside the bag. Shape 2 with a second thing to remember, so the table becomes two-dimensional.
Statedp[i][c] = the best value using the first i items with capacity c.
Choiceskip item i, or take it if it fits and pay its weight.
Recurrenceskip = dp[i-1][c], take = dp[i-1][c - w[i-1]] + val[i-1]. Keep the larger. Row 0 is all zeros: no items, no value.
def knapsack(w, val, cap):
n = len(w)
dp = [[0] * (cap + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for c in range(cap + 1):
dp[i][c] = dp[i - 1][c] # skip item i
if w[i - 1] <= c:
take = dp[i - 1][c - w[i - 1]] + val[i - 1]
if take > dp[i][c]:
dp[i][c] = take
return dp[n][cap]
# knapsack([1,3,4,5], [1,4,5,7], 7) -> 9 (items of weight 3 and 4)
int knapsack(int[] w, int[] val, int cap) {
int n = w.length;
int[][] dp = new int[n + 1][cap + 1];
for (int i = 1; i <= n; i++) {
for (int c = 0; c <= cap; c++) {
dp[i][c] = dp[i - 1][c];
if (w[i - 1] <= c) {
int take = dp[i - 1][c - w[i - 1]] + val[i - 1];
if (take > dp[i][c]) dp[i][c] = take;
}
}
}
return dp[n][cap];
}
Shape 5 · asked as "Longest Common Subsequence"
Two sequences, one table
Two strings. Find the longest sequence of characters that appears in both, in order, not necessarily next to each other. Whenever a problem hands you two sequences, the state is one index into each: a grid.
Statedp[i][j] = the LCS length of the first i characters of a and the first j of b.
Choiceif the two current characters match, use them both; if not, drop one character from a or one from b.
Recurrencematch: dp[i][j] = dp[i-1][j-1] + 1. No match: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Row 0 and column 0 are zeros.
def lcs(a, b):
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][m]
# lcs("abcde", "ace") -> 3 the subsequence is "ace"
int lcs(String a, String b) {
int n = a.length(), m = b.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[n][m];
}
Shape 6 · asked as "Longest Increasing Subsequence"
Look back at everything
Find the length of the longest strictly increasing subsequence. Shape 1 looked back one or two places; here every earlier state is a candidate, so the inner loop runs over all of them. O(n squared), and that is the expected answer.
Statedp[i] = the length of the longest increasing subsequence that ends at index i.
Choicewhich earlier index j to sit on top of: any j with nums[j] < nums[i].
Recurrencedp[i] = 1 + max(dp[j]) over those j, or 1 if there is none. The answer is max(dp), not dp[n-1]: the best run may end anywhere.
def lis(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
return max(dp)
# lis([10, 9, 2, 5, 3, 7, 101, 18]) -> 4 dp = [1,1,1,2,2,3,4,4]
int lis(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] dp = new int[n];
Arrays.fill(dp, 1);
int best = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
}
if (dp[i] > best) best = dp[i];
}
return best;
}
Memoisation vs tabulation
Two ways to write the same DP. Memoisation is the recursion you would write anyway, plus a dictionary so nothing is computed twice: top-down. Tabulation fills an array from the smallest case upwards: bottom-up. Here is house robber, both ways, same answer.
Memoisation · top-down
def rob_memo(nums):
memo = {}
def best(i): # best money from houses 0..i
if i < 0:
return 0
if i in memo:
return memo[i]
memo[i] = max(best(i - 1), best(i - 2) + nums[i])
return memo[i]
return best(len(nums) - 1) # -> 12 on [2, 7, 9, 3, 1]
Tabulation · bottom-up
def rob_tab(nums):
n = len(nums)
dp = [0] * (n + 1)
dp[1] = nums[0]
for i in range(2, n + 1):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])
return dp[n] # -> 12 on [2, 7, 9, 3, 1]
Write memoisation whenthe recursion is obvious and the states are scattered or hard to order. It is also the fastest thing to produce in an interview: write brute-force recursion, add a dictionary, done.
Write tabulation whenthe states are a clean range and the input is big. No recursion means no stack limit, and the loop order is visible on the page. This is what most editorials show.
Filling a table by hand
On paper, in an interview, this is what convinces the interviewer. Take LCS of a = "abcde" and b = "ace". Draw a grid with one row per character of a plus a zero row, and one column per character of b plus a zero column.
Fill row 0 and column 0 with zeros. An empty string shares nothing with anything.
Go left to right, top to bottom. Every cell only ever looks up, left, and up-left, and all three are already filled.
Characters equal: copy the up-left cell and add 1. Not equal: copy the larger of the cell above and the cell to the left.
The answer is the bottom-right cell. To recover the actual subsequence, walk back: on a match, write the character and move up-left; otherwise move towards the bigger of up and left.
"" a c e
"" 0 0 0 0
a 0 1 1 1 a == a, so 0 + 1 = 1
b 0 1 1 1 b matches nothing, copy the best neighbour
c 0 1 2 2 c == c, so up-left 1 + 1 = 2
d 0 1 2 2
e 0 1 2 3 e == e, so up-left 2 + 1 = 3 <- answer
walk back from the corner: e (match), d, c (match), b, a (match) -> "ace"
The same drawing works for knapsack. Rows are items, columns are capacities 0 to cap, and every cell looks at the row above: straight up for skip, up and left by the item weight for take. Fill row by row, read the bottom-right corner.
The 5 mistakes
- 1
The wrong base casedp[0] for climbing stairs is 1, not 0: there is exactly one way to stand at the bottom, do nothing. Set the base by asking what the answer is for the smallest input, not by guessing zero.
- 2
Filling the table in the wrong orderEvery cell must be filled after the cells it reads. If dp[i][c] reads dp[i-1][c], the row loop must be outside. Write the recurrence first, then choose a loop order that makes its right-hand side already known.
- 3
Off-by-one on the table sizeFor n items the table has n + 1 rows, because row 0 means "no items". Then item i lives at index i - 1 in the array. Pick one convention on the first line and hold it for the whole function.
- 4
Sharing mutable state in memoisationA dictionary passed as a default argument, or a global memo reused across test cases, keeps answers from the previous input. Create the memo inside the function, every call.
- 5
Using DP where greedy is intendedCoin change with Indian coins looks greedy, and greedy is wrong in general: with coins 1, 3, 4 and amount 6, greedy takes 4 + 1 + 1, DP takes 3 + 3. Say this out loud in the interview; it is the reason DP exists.
Before you code, say two sentences out loud: "dp[i] is ..." and "at each state I choose between ...". If you cannot finish both, you do not have the state yet, and no amount of typing will fix that.