Dynamic programming is recursion that stopped recomputing. Write the brute-force recursion first, express the problem in terms of an index, do every possible thing at that index, then take the max, min or sum the question asks for. Once that runs, three mechanical steps turn it into the answer an interviewer wants: memoize it, tabulate it, then throw the table away. Thirteen lectures, and the same four steps every single time.
This is not a list of problems. It is 13 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
ASSUMEDStriver's recursion playlist, lectures 6 and 7, pick / not-pick and counting ways at the base case. DP 1 names them as the prerequisite in its opening minutes and every unit here leans on them.
12 PROBLEMS · 11 LINK TO A JUDGE · THE REST ARE CONCEPTS THE DRILLS COVER
Almost nobody fails a DP problem because they cannot fill a table. They fail because they cannot tell, from the statement, what the state should be. These six phrasings cover every problem in this deck, and the right-hand column is what each one permits you to write.
every route has to be counted, so you try them all and ADD. That is a sum recurrence
COUNT DP · base case returns 1O(n) or O(n·m)try every option at this index and keep the best, a min or max recurrence
OPTIMISATION DP · out-of-range returns ±∞O(n) or O(n·m)the only thing forbidden is the index you just came from, and the state already knows it
PICK / NOT-PICK · still one indexO(n)what is forbidden is one of k named choices, so the state has to carry WHICH, false friend of the card on its left
PICK / NOT-PICK · one extra dimensionO(n·k)each cell is reachable from exactly two others, so the table has the grid's own shape
DP ON GRIDS · dp[i][j] from up and leftO(n·m)no fixed origin means you loop the driver over every legal start and take the best
VARIABLE ENDPOINTS · answer is over a whole rowO(n·m)solving them separately double-counts anything shared, so move them together
MULTI-AGENT DP · one index per moverO(n·m²)Read the target complexity off the bounds before designing the state. A DP's cost is (number of states) × (work per state), so the constraint is telling you how many indices you are allowed. Type a bound and the row it lands in rings gold.
n ≤ 20 is the one band where plain recursion survives, and it is also the signal for bitmask DP, which this sheet does not cover in any of the four decks.
You write a recursion, it is correct, and it times out. Before reaching for a dp array, what has to be true of the problem?
Overlapping subproblems. Memoization only pays when the same call happens again. The mechanism is nothing more. A recursion whose branches never revisit a state (merge sort, say) gets nothing from a table however slow it is. The other half of the requirement, optimal substructure, is what lets you build the answer from subanswers at all.
A DP over an array of size n with n ≤ 10⁵. Your table is dp[i][j] over all pairs. What has gone wrong?
Read the bound before designing the state. n ≤ 10⁵ buys about O(n log n); an n² table is 10¹⁰ cells and will not fit in memory, let alone time. The constraint is telling you the state has ONE index. Doing this arithmetic first is the habit. The next slide is a ladder for it.
Memoized recursion. It compiles and returns a number. One line makes the table useless, which?
int f(int i, vector<int>& dp){ if(i <= 1) return i; if(dp[i] != -1) return dp[i]; int r = f(i-1,dp) + f(i-2,dp); return r; }
It reads the table and never writes it. Line 3 checks the cache and line 5 returns without filling it, so every lookup misses and the runtime stays exponential, while the code LOOKS memoized. Nothing crashes, nothing returns a wrong answer; it is simply as slow as the version you were replacing. Write it as return dp[i] = r; and the store cannot be forgotten.
Tabulation is usually preferred over memoization in an interview even when both are O(n). Why?
The stack. Both use an O(n) table; memoization ALSO uses O(n) stack frames, and at n = 10⁶ that is where it dies. Tabulation is a loop, so the stack term disappears entirely, and only once the table is a loop can you notice it reads two cells and throw the table away too.
Thirteen lectures, 6h 43m. The first six build the method on a single line of cells; the last seven put a second index on it and then a third. Unit 10 has no sheet row. It is the lecture where counting turns into optimising, and skipping it would leave the three units after it resting on an argument nobody made.
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
Memoization, tabulation and space optimisation are three forms of one recurrence
WHY DOES A CORRECT RECURSION TAKE FOREVER, AND WHAT EXACTLY FIXES IT?
The lecture names the exact condition that makes a problem worth memoizing. What is it called?
When f(2) is computed under f(4) and again under f(3), it is the SAME subproblem. 'the second Fibonacci number is going to be the same at any instance in the entire program'. That repetition is what memoization removes. Optimal substructure is real and also required, but it is not the word the lecture uses here.
Memoized Fibonacci is O(n) time. What is its SPACE, as the lecture breaks it down?
Two separate costs, and the lecture insists on naming both: the dp array is O(n) AND the recursion stack is O(n). This matters because it is exactly the stack term that tabulation deletes, which is the whole reason the next step exists.
This is the memoized Fibonacci from the lecture. One line will crash or silently return garbage. Which one?
int f(int n, vector<int>& dp){ if(n <= 1) return n; if(dp[n] != -1) return dp[n]; return dp[n] = f(n-1,dp) + f(n-2,dp); } int fib(int n){ vector<int> dp(n, -1); return f(n, dp); }
vector<int> dp(n, -1) holds indices 0..n-1, but f(n) writes dp[n]. The lecture is explicit that the array is declared with size n+1 precisely because the subproblems run 0 through n inclusive. Off by one, and it is the single most common way this code dies.
After tabulation, the lecture space-optimises to two variables. What makes that legal for Fibonacci but NOT for every tabulated DP?
prev/prev2 works because dp[i] depends on dp[i-1] and dp[i-2] and nothing older. The moment a recurrence reaches further back (or reaches an arbitrary index, as Frog Jump with K does) the whole row has to stay alive. Space optimisation is a property of the RECURRENCE, not a step you always get to take.
The same f(n) = f(n-1) + f(n-2), four times. Watch the call tree for fib(5) shrink as each step is applied, and watch what each step actually buys: memoization deletes the repeated calls, tabulation deletes the stack, and space optimisation deletes the table. Nothing about the recurrence changes.
There is no statement to read. This row is the METHOD. Every later problem is these four steps applied to a recurrence you have just written.
A recursion that revisits the same subproblem is doing the same work twice. Store each answer the first time (memoization) and the tree collapses to a spine. Rewrite that as a bottom-up loop (tabulation) and the recursion stack goes too. Notice the loop only reads the last cell or two, keep those in variables, and the table goes as well.
// 1 - plain recursion: O(2^n) int f(int n) { return n <= 1 ? n : f(n-1) + f(n-2); } // 2 - memoization: O(n) time, O(n) table + O(n) stack int f(int n, vector<int>& dp) { if (n <= 1) return n; if (dp[n] != -1) return dp[n]; return dp[n] = f(n-1, dp) + f(n-2, dp); // WRITE, not just return } // 3 - tabulation: O(n) time, O(n) table, no stack vector<int> dp(n+1); // n+1, not n dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2]; // 4 - space optimised: O(n) time, O(1) space int p2 = 0, p1 = 1; for (int i = 2; i <= n; i++) { int c = p1 + p2; p2 = p1; p1 = c; }
# 1 - plain recursion: O(2^n) def f(n): return n if n <= 1 else f(n-1) + f(n-2) # 2 - memoization: O(n) time, O(n) table + O(n) stack def f(n, dp): if n <= 1: return n if dp[n] != -1: return dp[n] dp[n] = f(n-1, dp) + f(n-2, dp) # WRITE, not just return return dp[n] # 3 - tabulation: O(n) time, O(n) table, no stack dp = [0] * (n + 1) # n+1, not n dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] # 4 - space optimised: O(n) time, O(1) space p2, p1 = 0, 1 for _ in range(2, n + 1): p2, p1 = p1, p1 + p2
Reading the table and forgetting to write it. if(dp[i]!=-1) return dp[i]; followed by return f(i-1)+f(i-2); compiles, returns the right answer, and is still exponential. Write return dp[i] = … and it cannot happen.
Writing a 1D recurrence from the way a problem branches
HOW MANY DISTINCT WAYS ARE THERE TO CLIMB n STAIRS TAKING 1 OR 2 AT A TIME?
Climbing Stairs counts ways rather than optimising. What does the base case return, and why?
The lecture stops and points back at recursion lecture 7 for this exact reason. When you are counting ways, arriving at the target is itself one valid way, so the base case contributes a 1 that gets summed up the tree. Return 0 and every count collapses to zero.
The lecture gives the tell for spotting a DP problem in the statement. Which phrasing is it?
Count-all-ways and find-the-min-or-max are the two shapes that mean 'try every option, then combine', which is recursion, which becomes DP once the subproblems repeat. This is the recognition skill the SIGNALS slide is built from.
n = 4, and you may climb 1 or 2 steps. Step the table. What is dp[4]?
dp[0]=1, dp[1]=1, then each cell is the sum of the two below it: dp[2]=2, dp[3]=3, dp[4]=5. It is Fibonacci wearing a different problem statement, which is the point of putting this lecture second.
Climbing stairs, n = 8. Every cell is the sum of the two below it, and the base case is a 1 because arriving is itself one way. Step it and watch the two cells each new answer reads. That pair is the entire reason this collapses to two variables later.
“In how many distinct ways” plus a small set of moves. Counting, not optimising, so the children get ADDED, and the base case contributes a 1.
To be standing on stair i you arrived from i−1 or from i−2, and those two sets of routes are disjoint. So the count at i is the sum of the counts below it. The base case is 1 because arriving is itself one complete way. Return 0 and every count collapses.
int climbStairs(int n) { int prev2 = 1, prev1 = 1; // dp[0] = dp[1] = 1 for (int i = 2; i <= n; i++) { int cur = prev1 + prev2; // one step below, or two prev2 = prev1; prev1 = cur; } return prev1; }
def climbStairs(n): prev2 = prev1 = 1 # dp[0] = dp[1] = 1 for _ in range(2, n + 1): prev2, prev1 = prev1, prev1 + prev2 return prev1
Returning 0 at the base case, out of habit from optimisation problems. In a COUNT, reaching the target is one way and must contribute 1. Every answer becomes 0 and it looks like the recurrence is wrong when the base case is.
When the transition carries a cost rather than a count
THE FROG PAYS |h[i] − h[j]| TO JUMP. WHAT IS THE CHEAPEST WAY DOWN THE ARRAY?
Frog Jump swaps counting for optimising. What does its base case at index 0 return?
The frog starts at index 0, so standing there has cost nothing. Returning 1 here (the Climbing Stairs reflex) poisons every path with a phantom unit of energy. The base case follows the QUANTITY being computed, not the shape of the recursion.
The two-jump branch of Frog Jump. One line is wrong. Which one?
int f(int i, vector<int>& h, vector<int>& dp){ if(i == 0) return 0; if(dp[i] != -1) return dp[i]; int one = f(i-1,h,dp) + abs(h[i]-h[i-1]); int two = f(i-2,h,dp) + abs(h[i]-h[i-2]); return dp[i] = min(one, two); }
At i == 1 the two-step jump reads h[-1] and recurses into f(-1). The lecture guards it explicitly: the second jump is only legal when i > 1. The fix is int two = INT_MAX; if(i > 1) two = ..., INT_MAX rather than 0, so an illegal jump can never win the min.
When you guard the illegal two-step jump, what should the unused branch be initialised to?
This is a min problem, so a disallowed option must be made unattractive, not cheap. Initialise it to 0 and the min will pick the jump that never happened. The mirror of this trap returns at Minimum Path Sum, where an out-of-grid cell has to return a huge value for the same reason.
A cost attached to the MOVE rather than to the cell, and “minimum total energy”. Optimisation, so the children get min-ed and the base case is 0.
Standing on stone i, you got there from i−1 or i−2 and paid the height difference. So the cheapest way to i is the cheaper of those two arrivals plus its jump cost. The frog starts on stone 0 having spent nothing, which is why this base case is 0 and the stairs one was 1.
int frogJump(vector<int>& h) { int n = h.size(); int prev2 = 0, prev1 = 0; // dp[0] = 0: no energy spent yet for (int i = 1; i < n; i++) { int one = prev1 + abs(h[i] - h[i-1]); int two = INT_MAX; // NOT 0 - an illegal jump must never win if (i > 1) two = prev2 + abs(h[i] - h[i-2]); int cur = min(one, two); prev2 = prev1; prev1 = cur; } return prev1; }
def frogJump(h): prev2 = prev1 = 0 # dp[0] = 0 for i in range(1, len(h)): one = prev1 + abs(h[i] - h[i-1]) two = float('inf') # NOT 0 if i > 1: two = prev2 + abs(h[i] - h[i-2]) prev2, prev1 = prev1, min(one, two) return prev1
Initialising the illegal two-step jump to 0 instead of INT_MAX. The min then always picks the jump that could not be made, and the answer comes out too small, a plausible number from code that reads correctly.
Generalising a fixed branching factor to a loop over k
THE FROG MAY NOW JUMP UP TO k STEPS. WHAT CHANGES, AND WHAT DOES IT COST?
Frog Jump with K distances replaces two hard-coded branches with a loop over j = 1..k. What must be checked inside that loop?
With k arbitrary, the loop will happily walk past the start of the array. The lecture stops on this: i-j must stay >= 0, and once it would not, you break out. It is the same guard as lecture 3, generalised, which is exactly why this lecture is short.
Frog Jump (k=2) space-optimises to two variables. Why can't Frog Jump with K distances?
prev/prev2 works only when the recurrence reaches back a fixed, tiny distance. Here it reaches back up to k, so you need the last k values live, which for large k is the whole array. This is the concrete case that makes unit 1's fourth drill real rather than theoretical.
The same statement as the previous row with the fixed 2 replaced by a parameter k. A fixed branching factor becoming a variable one always means a loop.
Nothing conceptual changes. Where there were two candidate predecessors there are now up to k, so the two hand-written branches become a loop over j = 1..k with the same guard applied once instead of twice. What DOES change is the space: the recurrence now reaches k cells back, so the row has to stay alive.
int frogJumpK(vector<int>& h, int k) { int n = h.size(); vector<int> dp(n, 0); // the whole row must stay alive now for (int i = 1; i < n; i++) { int best = INT_MAX; for (int j = 1; j <= k; j++) { if (i - j < 0) break; // the guard: never a negative index best = min(best, dp[i-j] + abs(h[i] - h[i-j])); } dp[i] = best; } return dp[n-1]; }
def frogJumpK(h, k): n = len(h) dp = [0] * n # the whole row must stay alive now for i in range(1, n): best = float('inf') for j in range(1, k + 1): if i - j < 0: break # the guard: never a negative index best = min(best, dp[i-j] + abs(h[i] - h[i-j])) dp[i] = best return dp[n-1]
Assuming the space optimisation from the previous problem still applies. It does not, and the reason is worth internalising: space optimisation is a property of how far the RECURRENCE REACHES, not of the problem it came from.
The subsequence recurrence, and why adjacency forbids i−1
PICK NUMBERS WITH NO TWO ADJACENT. WHAT IS THE LARGEST SUM YOU CAN MAKE?
The lecture calls this the pick / not-pick pattern. When you PICK index i, which index does the recursion go to?
Picking i forbids i-1 by the adjacency rule, so the next legal choice is i-2. Not picking sends you to i-1. That asymmetry IS the problem. Get it backwards and you have written plain maximum-subarray.
Maximum sum of non-adjacent elements. One line steps out of bounds. Which one?
int f(int i, vector<int>& a, vector<int>& dp){ if(i == 0) return a[0]; if(i < 0) return 0; if(dp[i] != -1) return dp[i]; int pick = a[i] + f(i-2, a, dp); int notPick = 0 + f(i-1, a, dp); return dp[i] = max(pick, notPick); }
Not out of bounds in the array, out of bounds in the DP TABLE. At i == 1, f(-1) is reached and dp[i] on the way back writes dp[-1]. The i<0 guard on line 3 catches the read but the lecture warns about the index itself: 'what if index was 1 and you did 1 minus 2 and you went on to a negative index'. Order the two base cases i<0 first, or clamp the call.
a = [2, 7, 9, 3, 1]. Fill the table left to right. What is the answer?
dp[0]=2, dp[1]=max(7,2)=7, dp[2]=max(9+2,7)=11, dp[3]=max(3+7,11)=11, dp[4]=max(1+11,11)=12. Picking 2, 9 and 1 gives 12. The tempting 7+3 line is a trap the table kills for you.
[2, 7, 9, 3, 1], no two adjacent. One row again, but now PICK reaches back to i-2 and NOT-PICK to i-1. The greedy answer. Take 7 and 3. loses, and you can watch the table refuse it.
“No two adjacent” over a linear array, maximising a sum. The moment a choice here forbids a choice next door, you are in pick / not-pick.
At each element you either take it, which forbids its neighbour, so you continue from i−2, or you skip it and continue from i−1. That asymmetry is the entire problem. Carried forward as two running values, ‘best having just taken’ and ‘best having just skipped’, it is a single pass.
int rob(vector<int>& a) { int take = 0, skip = 0; // best ending here having taken / skipped for (int x : a) { int newTake = skip + x; // taking x forbids the previous element skip = max(skip, take); // skipping x keeps the better of the two take = newTake; } return max(take, skip); }
def rob(a): take = skip = 0 for x in a: take, skip = skip + x, max(skip, take) return max(take, skip)
Reaching a negative index. At i = 1, picking sends you to f(−1), and in the memoized version it also WRITES dp[−1] on the way back. Order the base cases so i < 0 is caught before anything indexes the table.
Breaking a circular constraint into two linear runs
THE HOUSES ARE IN A CIRCLE, SO THE FIRST AND LAST ARE NEIGHBOURS. NOW WHAT?
House robber II is the circular version. How does the lecture reduce it to a problem already solved?
First and last are adjacent on a circle, so they can never both be taken. Excluding one or the other covers every legal case, and each half is exactly the previous lecture's function. This is the deck's clearest example of reduction rather than a new recurrence.
The lecture stops on one word in the constraints and calls it 'very important'. Which?
Non-negative values are what make 'rob nothing' a safe floor of 0 and let the not-pick branch contribute a plain 0. Allow negatives and the whole framing shifts. Reading the constraints for this kind of word is the habit the CONSTRAINTS slide is built to teach.
n = 1. A single house on a circle. What does the two-run reduction do, and is it right?
Excluding the first leaves nothing; excluding the last leaves nothing; max(0,0)=0 while the answer is a[0]. The reduction is sound for n>=2 and needs an explicit n==1 guard. The lecture handles it in code almost in passing, which is exactly why it is worth a drill.
The previous problem with the array bent into a circle, so the first and last elements are now neighbours. A circular constraint over a solved linear problem is almost always two linear runs.
On a circle the first and last houses can never both be taken. So every valid answer either leaves out the first or leaves out the last, and each of those is exactly the linear problem you already solved. Run it twice and take the better. No new recurrence is written at all.
int robLinear(vector<int>& a, int lo, int hi) { int take = 0, skip = 0; for (int i = lo; i <= hi; i++) { int newTake = skip + a[i]; skip = max(skip, take); take = newTake; } return max(take, skip); } int rob(vector<int>& a) { int n = a.size(); if (n == 1) return a[0]; // the circle degenerates - guard it return max(robLinear(a, 0, n-2), // drop the last house robLinear(a, 1, n-1)); // drop the first house }
def rob(a): def linear(seq): take = skip = 0 for x in seq: take, skip = skip + x, max(skip, take) return max(take, skip) if len(a) == 1: return a[0] # the circle degenerates - guard it return max(linear(a[:-1]), linear(a[1:]))
Forgetting the single-house case. Both slices come out empty, max(0, 0) is 0, and the answer should have been a[0]. The reduction is sound for n ≥ 2 and silently wrong for n = 1.
A second changing parameter, and why it becomes a second dimension
EACH DAY PICK ONE OF THREE TASKS, NEVER THE SAME AS YESTERDAY. MAXIMISE MERIT.
This lecture states the three steps for writing ANY DP recurrence. What is step one?
Express in terms of index -> do all possible stuffs on that index -> take max or min or sum per the question. The lecture calls this out as the reusable method, and it is the sentence the whole deck is organised around. It is why unit 7 is titled THE 2D TURN rather than 'Ninja's Training'.
Why does Ninja's Training need a SECOND dimension when the 1D problems did not?
The day alone does not determine the subproblem. You also need to know which task was done last, because it is forbidden today. A parameter that changes AND affects the answer is a dimension. That test is the whole content of this lecture and it generalises to every 2D DP after it.
Ninja's Training, top-down. One line quietly allows an illegal schedule. Which one?
int f(int day, int last, vector<vector<int>>& p, vector<vector<int>>& dp){ if(day == 0){ int mx = 0; for(int t = 0; t < 3; t++) if(t != last) mx = max(mx, p[0][t]); return mx; } if(dp[day][last] != -1) return dp[day][last]; int mx = 0; for(int t = 0; t < 3; t++) mx = max(mx, p[day][t] + f(day-1, t, p, dp)); return dp[day][last] = mx; }
The base case correctly skips t == last, but the recursive loop forgot to. It lets the ninja repeat yesterday's task, and because the value can only go up, the bug always inflates the answer rather than crashing. Wrong output that looks plausible is exactly what the TRAPS slide is reserved for.
Ninja's Training. The day alone does not determine the answer: yesterday's task is forbidden today, so the state has to carry it. Rows are days, columns are which task was done last, and that second axis is what a second dimension actually is.
A choice per day, and today's choice constrained by yesterday's. The instant a past decision affects a future one, the state has to carry it.
The day alone does not determine the subproblem. You also need to know which task was done last, because it is forbidden now. A parameter that changes AND affects the answer is a dimension, so the table becomes dp[day][last]. That test is the whole content of this problem and it generalises to every 2D DP after it.
int ninjaTraining(vector<vector<int>>& p) { int n = p.size(); vector<int> prev(3); for (int t = 0; t < 3; t++) prev[t] = p[0][t]; for (int day = 1; day < n; day++) { vector<int> cur(3); for (int last = 0; last < 3; last++) { int best = 0; for (int t = 0; t < 3; t++) if (t != last) best = max(best, prev[t]); // t != last, EVERY loop cur[last] = p[day][last] + best; } prev = cur; } return max({prev[0], prev[1], prev[2]}); }
def ninjaTraining(p): prev = list(p[0]) for day in range(1, len(p)): cur = [] for last in range(3): best = max([prev[t] for t in range(3) if t != last]) cur.append(p[day][last] + best) # t != last, EVERY loop prev = cur return max(prev)
Putting the t != last guard in the base case and forgetting it in the recursive loop. The ninja repeats yesterday's task, the total can only go UP, and the answer is plausibly too big rather than obviously broken.
Counting paths on a grid, and all four forms of the same answer
HOW MANY WAYS ARE THERE FROM THE TOP-LEFT TO THE BOTTOM-RIGHT, RIGHT AND DOWN ONLY?
For an m x n grid moving only right and down, the lecture derives the path LENGTH before writing any code. What is it?
Every path takes exactly m-1 downs and n-1 rights in some order, which is also why the closed-form answer is a binomial coefficient. Knowing the path length is what lets you sanity-check a table before trusting it.
Walking BACKWARD from (m-1, n-1), the recursion at cell (i, j) calls which two cells?
The lecture writes the recursion in reverse (from destination to origin), so a step 'up' is i-1 and a step 'left' is j-1. It matters because the base case then sits at (0,0) returning 1, and every guard is i > 0 / j > 0 rather than a bounds check against m and n.
A 3 x 3 grid, moving only right and down. Fill it. How many unique paths?
Row and column of 1s, then each interior cell is up + left: the last cell is 6. Check it against the path-length rule, 2 downs and 2 rights, choose 2 from 4, which is 6. Two independent derivations agreeing is how you trust a table.
A 3 × 3 grid, moving only right and down. Same recurrence shape as the stairs. each cell sums the two it can be reached from, but the two are now up and left. The first row and column are all 1s because there is exactly one way to walk a straight line.
A grid, movement restricted to right and down, and “how many unique paths”. Counting on a rectangle. The table has the grid's own shape.
Each cell can only be entered from above or from the left, and those two sets of routes are disjoint, so its count is their sum. Walking the recursion backwards from the destination makes the base case (0,0) return 1 and turns every bound into a simple i > 0 / j > 0 test.
int uniquePaths(int m, int n) { vector<int> prev(n, 0); for (int i = 0; i < m; i++) { vector<int> cur(n, 0); for (int j = 0; j < n; j++) { if (i == 0 && j == 0) { cur[j] = 1; continue; } // one way to stand still cur[j] = (j ? cur[j-1] : 0) // left, 0 if off-grid + (i ? prev[j] : 0); // up, 0 if off-grid } prev = cur; } return prev[n-1]; }
def uniquePaths(m, n): prev = [0] * n for i in range(m): cur = [0] * n for j in range(n): if i == 0 and j == 0: cur[j] = 1 # one way to stand still else: cur[j] = (cur[j-1] if j else 0) + (prev[j] if i else 0) prev = cur return prev[n-1]
On a counting problem the off-grid return is 0, and that is right here. Carry the habit into the next problem, where the combine is a min, and the illegal route becomes the cheapest one. The identity belongs to the OPERATOR.
One guard clause turns a count into a constrained count
THE SAME GRID, BUT SOME CELLS ARE BLOCKED. HOW MUCH OF THE CODE CHANGES?
Unique Paths II adds obstacles. What is the entire change to the recursion?
An obstacle cell contributes no paths, so it returns 0 and the sum above it does the rest. The lecture is blunt that this is a single-line addition to lecture 8, which is why the deck ships it as a code diff rather than a fresh derivation.
The lecture flags one thing that has nothing to do with obstacles and will still fail you. What?
Path counts blow past 32-bit fast, and the judge asks for the count mod 1e9+7. The lecture stops the code walkthrough to declare the modulus globally. It is not a DP idea at all, which is precisely why it gets forgotten.
Unique Paths II. One line puts the guard in the wrong place. Which one?
int f(int i, int j, vector<vector<int>>& g, vector<vector<int>>& dp){ if(i >= 0 && j >= 0 && g[i][j] == 1) return 0; if(i == 0 && j == 0) return 1; if(i < 0 || j < 0) return 0; if(dp[i][j] != -1) return dp[i][j]; int up = f(i-1, j, g, dp); int left = f(i, j-1, g, dp); return dp[i][j] = (up + left) % MOD; }
The obstacle check runs before the out-of-bounds check, so it has to re-test i and j itself, and if you ever drop that half of the condition, g[-1][j] reads off the end. The lecture's ordering is out-of-bounds first, then obstacle, then destination. Cheap to get right, silent when wrong.
The previous grid with some cells blocked. A constraint layered on a solved counting problem is usually one guard, not a new method.
A blocked cell can be part of no path, so it contributes 0, and the sum above and to the left of it does the rest automatically. Nothing else changes. What is easy to get wrong is not the DP but the ORDER of the base cases, and the modulus the judge asks for.
-int uniquePaths(int m, int n) {+int uniquePathsWithObstacles(vector<vector<int>>& g) {+ int m = g.size(), n = g[0].size(); vector<int> prev(n, 0); for (int i = 0; i < m; i++) { vector<int> cur(n, 0); for (int j = 0; j < n; j++) {- if (i == 0 && j == 0) { cur[j] = 1; continue; } // one way to stand still- cur[j] = (j ? cur[j-1] : 0) // left, 0 if off-grid- + (i ? prev[j] : 0); // up, 0 if off-grid+ if (g[i][j] == 1) { cur[j] = 0; continue; } // blocked: no paths+ if (i == 0 && j == 0) { cur[j] = 1; continue; }+ cur[j] = (j ? cur[j-1] : 0) + (i ? prev[j] : 0); } prev = cur; } return prev[n-1]; }
-def uniquePaths(m, n):+def uniquePathsWithObstacles(g):+ m, n = len(g), len(g[0]) prev = [0] * n for i in range(m): cur = [0] * n for j in range(n):- if i == 0 and j == 0:- cur[j] = 1 # one way to stand still+ if g[i][j] == 1:+ cur[j] = 0 # blocked: no paths+ elif i == 0 and j == 0:+ cur[j] = 1 else: cur[j] = (cur[j-1] if j else 0) + (prev[j] if i else 0) prev = cur return prev[n-1]
Testing g[i][j] == 1 before testing whether i and j are in range. It reads off the end of the grid, and because the read usually lands on live memory it does not crash. It returns a wrong count on some inputs and the right one on others.
Swapping the sum for a min turns a path count into a path optimisation
SAME WALK, BUT EACH CELL COSTS SOMETHING. WHAT IS THE CHEAPEST ROUTE ACROSS?
Minimum Path Sum turns counting into optimising. What must an out-of-grid cell return now?
The lecture states the requirement before the value: the return must be something that makes this path 'not considered'. In a min, that is a huge number. Return 0 (the answer that was correct when counting), and every illegal path becomes the cheapest one.
Same grid, same recursion, but Unique Paths returns 0 out of bounds and Minimum Path Sum returns 1e9. What decides?
An out-of-range return is the identity for whatever operation combines the children. For a sum that is 0; for a min it is +infinity; for a max it is -infinity. Learn it as the identity and you never have to memorise it per problem again.
This unit has no row on Striver's sheet. Why is it still in the deck?
Triangle, Falling Path Sum and Cherry Pickup II are all minimise-or-maximise problems, and this is where that turn is explained. The sheet skips it; skipping it in the deck would leave the next three units resting on an argument nobody made. It owns no problem slide precisely because it owns no sheet row.
Identical walk, identical table, one operator changed: the sum becomes a min and each cell adds its own cost. This is the turn every grid problem after it depends on, and it is also where an out-of-grid cell stops returning 0 and starts returning infinity.
When the start is pinned and the end is not
A TRIANGLE, STARTING AT THE APEX. ANY CELL OF THE LAST ROW IS A LEGAL FINISH.
Triangle is the FIXED start, VARIABLE end pattern. What does that change about the answer?
You always start at (0,0), but any cell of the last row is a legal finish, so the answer is the best over that row rather than one cell. This is the distinction the next lecture generalises, and the reason these two units sit in this order.
Triangle [[2],[3,4],[6,5,7],[4,1,8,3]]. Fill it bottom-up. What is the minimum path sum from the apex?
Bottom row stays [4,1,8,3]. Row 2 becomes [6+min(4,1), 5+min(1,8), 7+min(8,3)] = [7,6,10]. Row 1 becomes [3+min(7,6), 4+min(6,10)] = [9,10]. Apex is 2+min(9,10) = 11, via 2->3->5->1. Doing it bottom-up is what makes the 'variable ending point' disappear. The whole last row is just the base case.
For the space-optimised tabulation the lecture keeps a row alive. Which one?
Filling bottom-up, row i only ever reads row i+1, so one array plus a temporary is enough. 'this current row becomes the front row'. Same argument as prev/prev2 in unit 1, one dimension up.
A triangle, a fixed apex, and any cell of the last row a legal finish. Fixed start, variable end. The answer is one cell, but the base case is a whole row.
Filled bottom-up, the ‘variable ending point’ disappears entirely: the last row IS the base case, and each row above it takes the better of the two cells below. Because the shape narrows, the diagonal can never leave the triangle, so this is the one grid problem with no bounds check.
int minimumTotal(vector<vector<int>>& t) { int n = t.size(); vector<int> dp(t[n-1].begin(), t[n-1].end()); // base case IS the last row for (int i = n - 2; i >= 0; i--) for (int j = 0; j <= i; j++) dp[j] = t[i][j] + min(dp[j], dp[j+1]); // down, or diagonal return dp[0]; // start is fixed at the apex }
def minimumTotal(t): dp = list(t[-1]) # base case IS the last row for i in range(len(t) - 2, -1, -1): for j in range(i + 1): dp[j] = t[i][j] + min(dp[j], dp[j+1]) # down, or diagonal return dp[0] # start is fixed at the apex
Filling top-down and then hunting for the minimum of the last row. It works, but it needs the bounds handling the bottom-up version never has, and it obscures that the base case and the free endpoint are the same fact.
Both ends variable, the loop over every starting column
START AT ANY CELL OF THE FIRST ROW AND END ANYWHERE. NOW WHAT DOES THE DRIVER LOOK LIKE?
This lecture opens by naming what it generalises. What is the new freedom?
The lecture literally says so: lecture 11 did fixed start / variable end, and a commenter asked what happens when both are free. Nothing else changes, so this unit follows Triangle even though the sheet lists it first.
A variable STARTING cell changes the top-level call. How?
With no fixed origin, every cell of the first row is a candidate start, so the driver loops over them and takes the max. The dp table is shared across those calls, which is why this costs a loop and not a factor of m.
Matrix [[1,2,10,4],[100,3,2,1],[1,1,20,2],[1,2,2,1]], moving down / down-left / down-right, starting anywhere in row 0. What is the MAXIMUM falling path sum?
Start at 2 (row 0, col 1), take 100, then 1, then 2, for 105. The trap is starting at 10 because it is the biggest number in the first row; that path cannot reach 100 and tops out lower. A variable starting point means you loop over ALL of row 0 and let the table decide, never eyeball the best-looking start.
“Starting from any cell in the first row” and ending anywhere in the last. Both endpoints free, the freedom lives in the driver, not the state.
The recurrence is the same three-way step down that a triangle uses. What changes is that there is no single top-level call: every cell of the first row is a candidate start, and every cell of the last row a candidate finish. So the driver loops over the starts and the answer is taken over a whole row.
int minFallingPathSum(vector<vector<int>>& g) { int n = g.size(), m = g[0].size(); vector<int> prev(g[0].begin(), g[0].end()); // any cell of row 0 may start for (int i = 1; i < n; i++) { vector<int> cur(m); for (int j = 0; j < m; j++) { int best = prev[j]; if (j > 0) best = min(best, prev[j-1]); // bounds - a rectangle if (j < m - 1) best = min(best, prev[j+1]); // has straight edges cur[j] = g[i][j] + best; } prev = cur; } return *min_element(prev.begin(), prev.end()); // end anywhere }
def minFallingPathSum(g): m = len(g[0]) prev = list(g[0]) # any cell of row 0 may start for row in g[1:]: cur = [] for j in range(m): best = min(prev[max(0, j-1): j+2]) # bounds: a rectangle has edges cur.append(row[j] + best) prev = cur return min(prev) # end anywhere
Eyeballing the biggest number in the first row and starting there. A variable starting point means you loop over ALL of row 0 and let the table decide. The best-looking start routinely leads nowhere.
Two agents moving at once, and the third dimension that tracks both
ALICE AND BOB BOTH WALK DOWN THE GRID. HOW MANY CHERRIES CAN THEY COLLECT TOGETHER?
The lecture's single most emphasised point about Alice and Bob. What is it?
Solving separately double-counts every cell they both pass through. Moving them in lockstep (same row, two columns) is what lets a shared cell be counted once. This is the whole reason the state is 3D and the lecture calls it out as very important.
The state is (row, colAlice, colBob), three indices for a 2D grid. Why only three and not four?
Because they step in lockstep, both are always on the same row, so the row is one shared index and only the two columns vary independently. Recognising that a fourth parameter is redundant is what keeps this O(n*m*m) instead of far worse.
The lecture names two kinds of base case and insists on an order. Which comes first?
'Always write the out of bound first.' If the destination check runs first it can read a cell that is already off the grid. The same ordering bug is planted in unit 9's drill. It recurs because it is genuinely easy to get wrong.
Sheet difficulty says MEDIUM; LeetCode calls Cherry Pickup II HARD. What actually makes it harder than everything before it?
Alice has 3 moves and Bob has 3, so each state branches 3 x 3 = 9 ways and the inner step is a double loop. Nothing about the METHOD is new (express in terms of index, do all stuffs, take the max), which is why the sheet is comfortable calling it Medium. The volume is what bites.
Alice starts top-left, Bob top-right, both step down together. They share a row, so one row index serves both and only the two columns vary, three indices for a 2D grid. Watch the row where they meet: the cherry is counted once, which is the whole reason they cannot be solved separately and added.
Two agents traversing the same grid at the same time, collecting from it. Two things moving at once is never two independent problems.
Alice and Bob step down in lockstep, so they always share a row, one row index serves both and only the two columns vary. That shared row is what lets the transition say if a == b, count this cell once, and it is precisely the fact that solving them separately and adding would destroy.
int cherryPickup(vector<vector<int>>& g) { int n = g.size(), m = g[0].size(); vector<vector<int>> nxt(m, vector<int>(m, 0)), cur(m, vector<int>(m, 0)); for (int a = 0; a < m; a++) for (int b = 0; b < m; b++) nxt[a][b] = g[n-1][a] + (a == b ? 0 : g[n-1][b]); for (int r = n - 2; r >= 0; r--) { for (int a = 0; a < m; a++) for (int b = 0; b < m; b++) { int here = g[r][a] + (a == b ? 0 : g[r][b]); // shared: ONCE int best = INT_MIN; for (int da = -1; da <= 1; da++) for (int db = -1; db <= 1; db++) { // nine moves int na = a + da, nb = b + db; if (na < 0 || na >= m || nb < 0 || nb >= m) continue; best = max(best, nxt[na][nb]); } cur[a][b] = here + best; } nxt = cur; } return nxt[0][m-1]; // Alice left, Bob right }
def cherryPickup(g): n, m = len(g), len(g[0]) nxt = [[g[n-1][a] + (0 if a == b else g[n-1][b]) for b in range(m)] for a in range(m)] for r in range(n - 2, -1, -1): cur = [[0] * m for _ in range(m)] for a in range(m): for b in range(m): here = g[r][a] + (0 if a == b else g[r][b]) # shared: ONCE best = max(nxt[a+da][b+db] # nine moves for da in (-1, 0, 1) for db in (-1, 0, 1) if 0 <= a+da < m and 0 <= b+db < m) cur[a][b] = here + best nxt = cur return nxt[0][m-1] # Alice left, Bob right
Running the single-agent solution twice, once for Alice, once for Bob, and adding. Independently optimal paths cross, and every crossing gets counted twice. It gives a number that is too large and looks entirely reasonable.
A grid problem asks for the number of paths. Out of bounds should return…
0, the identity for a sum. An illegal route contributes no paths. Return 1 and you invent routes that do not exist. Compare with the next question: the value is decided by the OPERATOR that combines the children, never by the problem being a grid.
Same grid, but now it asks for the MINIMUM path sum. Out of bounds returns…
+∞, the identity for a min. Return 0 and the illegal route is the cheapest one and always wins. This is the single most common grid-DP bug and it produces a plausible small number rather than a crash, which is exactly what makes it expensive.
Which of these recurrences CANNOT be space-optimised to a constant number of variables?
The one that reaches back k. Space optimisation is a property of how far the recurrence REACHES, not of the problem. Reach two cells and two variables suffice; reach k and you must keep the last k. The grid recurrence reaches one row back, so it collapses to one row, not to a constant, but still a dimension cheaper.
You are told the answer may start at any cell of the first row. What changes?
Only the driver. The recurrence and the table are untouched; what changes is that there is no single top-level call. Loop over the legal starts, share one dp table across them, take the best. Recognising that a freedom lives in the DRIVER and not in the state is what keeps the state small.
Two agents walk a grid and you want the total collected. Why can you not solve each separately and add?
Shared cells. Independently optimal paths may cross, and the sum then double-counts every crossing. Moving them together in one recursion is what lets the transition say count this cell once if a == b, and it is why the state grows a third index rather than the problem splitting in two.
A statement from no lecture in this deck. Three hotels quote you a different rate for every one of the next n nights. You must stay somewhere each night and may not stay in the same hotel two nights running. Spend the least. What shape is the state?
This is the false friend, wearing different clothes. It reads like “no two adjacent”, which needs one index, but what is forbidden here has a NAME (that particular hotel), and a name does not fit in an index. The moment the forbidden thing is one of k things rather than the place you just left, the state grows a dimension: O(n·k), not O(n). The greedy option is the tempting one and it loses whenever tonight's cheapest hotel is the one that unlocks a far cheaper night tomorrow, which is why the rates have to differ per night for the question to have any teeth. That is Ninja's Training with the nouns swapped, and swapping the nouns is exactly what an interviewer does.
Another you have not seen. n ≤ 200000 shelves stand in a row, each worth a restock bonus, and you may not restock two adjacent shelves. Collect the most. One of these is dead before you write a line of it, which, and why?
The bound killed it, not the recurrence. n ≤ 2·10⁵ buys roughly O(n log n); a table over pairs is 4·10¹⁰ cells, which is out of memory long before it is out of time. Read the constraint FIRST and it tells you how many indices you are allowed. Here, one. The other three fail for reasons you would only find later: plain recursion is exponential, and greedy loses on [5, 1, 1, 5] by taking 5 + 1 instead of 5 + 5.
None of these crash. Every one returns a number that looks like an answer, a table that is never written, a min that prefers a move nobody could make, a guard that only fires in the base case. Expense comes from exactly that.
if(dp[i]!=-1) return dp[i]; then return f(i-1)+f(i-2);. Every lookup misses, the answer is right, and the runtime is still exponential. Always write return dp[i] = … so storing cannot be skipped.
The subproblems run 0..n inclusive, so the array needs n+1 slots. Off by one, and it is either a crash or. Worse, in release builds, a silently wrong read.
A jump that cannot be made, or a cell off the grid, must be made UNATTRACTIVE. Return 0 and the min picks the move that never happened. Use a large value for min, a very negative one for max, the identity of the operator, not a habit.
Ninja's Training forbids repeating yesterday's task. Put t != last in the base case and forget it in the loop and the answer only ever goes UP, a plausible number that is too big, from code that reads correctly.
if(g[i][j]==1) return 0; above the i<0 guard reads off the end of the grid. Order is always: out of bounds, then blocked, then destination.
Path counts overflow 32 bits quickly and the judge wants the answer mod 1e9+7. Nothing about this is a DP idea, which is exactly why it is the one that gets left out.
The four steps, then every recurrence shape in this deck with its cost and the one line that selects it. This is the night-before page.
Express the problem in terms of an index, do every possible thing at that index, then take the max, min or sum the question asked for. Once that recursion runs, memoize it, tabulate it, and throw the table away, and the only judgement in the whole sequence is how far back the recurrence reaches. Thirteen lectures, one line of cells that became a rectangle and then grew a third index. Deck II takes the same four steps into subsequences and knapsack, where the second index is a running SUM rather than a position.
Deck 1 of 4. Lectures DP 1-13 of 56; DP 14-56 are decks II-IV. Twelve of the sheet's 55 rows. DP 10 (Minimum Path Sum) is a lecture with no sheet row and runs as a concept unit. Every drill is sourced from its lecture transcript and cites it; every bench fills in numbers the build re-derived and asserted.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.