Two halves, and the second is the only genuinely new idea in the whole of step 16. LIS is still pick / not-pick — you just carry which element you last took, and one lecture replaces the whole table with a binary search. Partition DP is different in kind: you stop choosing what to take and start choosing where to cut, then solve both sides and combine. Every remaining hard DP an interviewer asks is one of these two.
This is not a list of problems. It is 16 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
ASSUMEDDecks I to III of this step. The LIS half is pick / not-pick with the PREVIOUS choice carried; the partition half is the one genuinely new idea in step 16 — you choose a split point rather than an element, and both sides recurse.
16 PROBLEMS · EVERY ONE LINKS TO A JUDGE TO SOLVE
Seven of these rows are pick / not-pick with the previous choice carried. The other nine stop choosing elements altogether and choose a split point instead. Reading which of the two a statement is asking for, before writing anything, is what this whole deck is for.
pick / not-pick where the pick is conditional on what you last took
LIS · state carries the previous indexO(n²)the O(n²) table will not fit, so keep the smallest tail per length and binary search it
PATIENCE · tails array, O(n log n)O(n log n)no element to pick — you choose a SPLIT, recurse both sides and combine at the cut
PARTITION DP · loop over every k in (i, j)O(n³)take a valid prefix, pay for it, recurse on the remainder — one index, not two
FRONT PARTITION · O(n²)O(n²)ask what happens LAST rather than first, so the sides stay independent
REVERSE THE QUESTION · burst balloonsO(n³)build each cell from the neighbours already computed, or carry heights row by row
GRID DP · min of three, or a histogram + stackO(n·m)Partition DP is O(n³) — n² ranges, each looping over n cut points — so it only survives while n is around a hundred. That is the tightest bound in the whole of step 16, and a small n beside a parenthesisation problem is itself a strong hint about which pattern is wanted.
The LIS half is the opposite story: at n = 10⁵ the O(n²) table is impossible and the binary-search form is the only way through — which is why the sheet gives it a row.
Every DP in the first three decks chose an ELEMENT — take it or skip it. What does partition DP choose instead?
A cut, not an element. That is the one genuinely new idea in step 16, and it is why the state becomes a RANGE (i, j) rather than a position. The loop over cut points inside a two-index state is the pattern's signature — see it and you know what you are looking at.
LIS carries the previous index in its state, giving n × (n+1) states. The tabulated O(n²) form drops that. What does dp[i] mean there?
Ending exactly at i. That reformulation is what removes the second index — and it is why the answer is the MAXIMUM over the array rather than its last cell. The same 'the answer is not the corner' shape as longest common substring in deck III.
Matrix chain multiplication. It runs and returns a number that is too small. Which line?
int f(int i, int j, vector<int>& d, vector<vector<int>>& dp){ if(i == j) return 0; if(dp[i][j] != -1) return dp[i][j]; int best = INT_MAX; for(int k = i; k < j; k++){ int cost = f(i, k, d, dp) + f(k+1, j, d, dp); best = min(best, cost); } return dp[i][j] = best; }
The combine term is missing. Splitting is free in this code, so the answer is the sum of the sub-costs and nothing else — always too small, always a plausible number, and the recursion structure looks perfect. d[i-1]*d[k]*d[j] is what pays for joining the halves.
Burst Balloons cannot be solved by asking which balloon to burst FIRST. Why not?
The sides stop being subproblems. Burst a middle balloon and its left and right neighbours become adjacent, so neither half can be solved alone. Asking which is burst LAST fixes it: its neighbours are then the range's fixed boundaries, and the halves are independent again.
Sixteen lectures, 6h 06m, sixteen sheet rows. Units 01 to 07 are LIS — one table, one predicate swapped at a time, and one lecture that throws the table away entirely. Units 08 to 14 are partition DP, the one genuinely new idea in step 16. Units 15 and 16 close on two grid problems, the last deliberately easy.
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.
Pick / not-pick where the pick depends on what you last took
WHAT IS THE LONGEST RUN OF INCREASING VALUES YOU CAN PULL OUT, IN ORDER?
Why does the state need a second index beyond the current position?
Pick / not-pick again, but the pick branch is CONDITIONAL — you may only take a[i] if it exceeds what you last took. So the state carries the previous index, which is why the classic formulation is f(i, prev) over n × (n+1) states.
The lecture stresses what a subsequence is NOT. Which of these is not one of [9, 2, 5]?
Order is preserved in a subsequence; only skipping is allowed. He says it explicitly — 'five and two have swapped places, thereby it's not a subsequence'. That constraint is what makes the previous element the right thing to carry.
The O(n²) tabulated form uses dp[i] = the LIS ENDING at i. How is the answer read off?
A cell holds the best subsequence ending exactly there, and the best one may end anywhere — the same 'answer is not the corner' shape as longest common substring in deck III. Reading dp[n-1] gives only the subsequences forced to include the last element.
[10, 9, 2, 5, 3, 7, 101, 18]. Each cell is the longest increasing run ending exactly there, built by looking back at every smaller element before it. Watch which earlier cell each answer extends, and note the answer is the largest cell, not the last one.
“Longest increasing subsequence”. Pick / not-pick again — but whether you MAY pick depends on what you last took, which is what puts a second thing in the state.
Reformulate: let dp[i] be the longest increasing run ENDING exactly at i. Then every earlier element smaller than a[i] offers a chain to extend, and you take the best. That reformulation is what removes the 'previous index' from the state — and it is why the answer is the maximum over the array rather than its last cell.
int lengthOfLIS(vector<int>& a) { int n = a.size(); vector<int> dp(n, 1); // every element is a chain of one for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) if (a[j] < a[i]) // may this chain be extended? dp[i] = max(dp[i], dp[j] + 1); return *max_element(dp.begin(), dp.end()); // the MAX, never dp[n-1] }
def lengthOfLIS(a): n = len(a) dp = [1] * n # every element is a chain of one for i in range(n): for j in range(i): if a[j] < a[i]: # may this chain be extended? dp[i] = max(dp[i], dp[j] + 1) return max(dp) # the MAX, never dp[n-1]
Returning dp[n−1]. Each cell is the run ENDING there, so that answers 'the longest run that must include the last element' — a smaller number that happens to be right whenever the array ends on its own best chain.
One extra integer per cell buys the whole sequence back
THE LENGTH IS EASY. HOW DO YOU RECOVER THE SUBSEQUENCE ITSELF?
To reconstruct the actual subsequence, what does the O(n²) fill also record?
A parent array — one extra integer per cell. Then walk it backwards from the index holding the maximum and reverse. Storing whole subsequences in cells is O(n²) memory for information one integer already implies.
Where does the backward walk START?
The chain ends where dp is largest, not at the array's end and not at the array's largest element. Track that index while filling; starting anywhere else reconstructs a shorter chain and prints it with total confidence.
Why can the binary-search O(n log n) version NOT print the subsequence directly?
The tails array is the right LENGTH but its contents may never have appeared together as a subsequence. Reconstructing from it needs a separate parent array anyway — which is why the printing lecture stays on the O(n²) table.
“Print” or “return the subsequence”. The table holds the length; one extra integer per cell holds the route.
While filling, record which earlier index each cell extended. That parent array is a linked list running backwards through the best chain — walk it from the index holding the maximum and reverse. Storing whole subsequences in cells costs O(n²) memory for what one integer already implies.
vector<int> printLIS(vector<int>& a) { int n = a.size(), best = 0, at = 0; vector<int> dp(n, 1), parent(n); for (int i = 0; i < n; i++) { parent[i] = i; // its own parent = chain starts here for (int j = 0; j < i; j++) if (a[j] < a[i] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; parent[i] = j; // remember who we extended } if (dp[i] > best) { best = dp[i]; at = i; } // track the ARGMAX } vector<int> out; while (parent[at] != at) { out.push_back(a[at]); at = parent[at]; } out.push_back(a[at]); reverse(out.begin(), out.end()); return out; }
def printLIS(a): n = len(a) dp, parent = [1] * n, list(range(n)) # own parent = chain starts here best, at = 0, 0 for i in range(n): for j in range(i): if a[j] < a[i] and dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 parent[i] = j # remember who we extended if dp[i] > best: best, at = dp[i], i # track the ARGMAX out = [] while parent[at] != at: out.append(a[at]); at = parent[at] out.append(a[at]) return out[::-1]
Starting the backward walk at n−1. The chain ends wherever dp is largest, which is usually not the array's end and is never guaranteed to be its largest VALUE either.
Replacing the whole table with a binary search
n IS 10⁵ AND THE O(n²) TABLE IS IMPOSSIBLE. WHAT REPLACES IT?
What does each cell of the maintained array actually hold?
The SMALLEST tail, because a smaller tail is never worse — anything that can extend a larger tail can extend a smaller one. That is the whole invariant, and it is why the array stays sorted and binary search applies.
A new element arrives that is not larger than every tail. What happens?
Binary search for the first tail not less than it and overwrite. The array's LENGTH does not change — you have improved a run of that length without lengthening anything. Appending here is the bug that inflates the answer.
The lecture warns the array is not the answer. What is it good for?
Overwriting tails means the array can end up holding elements that never formed a subsequence together. The length is always right; the contents are working state. Printing it is the classic misuse of this algorithm.
The same array, O(n log n). This row holds the smallest possible tail of an increasing run of each length, so it stays sorted and binary search applies. A value either APPENDS. The longest run grew, or overwrites a tail, improving a run without lengthening it. Its length is the answer; its contents are working state.
LIS again, but with n up to 10⁵. The O(n²) table is 10¹⁰ cells — so the constraint itself is telling you to throw the table away.
Keep an array where cell k holds the SMALLEST possible tail of an increasing run of length k+1. A smaller tail is never worse, because anything that can extend a larger one can extend it too. That invariant keeps the array sorted, which makes binary search legal — and each element either appends (the longest run grew) or overwrites a tail (a run of that length just got easier to extend).
int lengthOfLIS(vector<int>& a) { vector<int> tails; // smallest tail per run length for (int x : a) { auto it = lower_bound(tails.begin(), tails.end(), x); if (it == tails.end()) tails.push_back(x); // longer: APPEND else *it = x; // improve a tail } return tails.size(); // the LENGTH. the contents are NOT the answer }
from bisect import bisect_left def lengthOfLIS(a): tails = [] # smallest tail per run length for x in a: k = bisect_left(tails, x) if k == len(tails): tails.append(x) # longer than everything: APPEND else: tails[k] = x # improve a tail, same length return len(tails) # the LENGTH. the contents are NOT the answer
Printing the tails array as the answer. Overwriting means it can end up holding elements that never appeared together as a subsequence — the LENGTH is always right and the sequence is fiction.
The same table with the comparison swapped
LARGEST SUBSET WHERE EVERY PAIR DIVIDES. HOW IS THAT AN LIS PROBLEM?
Why does sorting the array first make this an LIS problem?
Once sorted, if a divides b and b divides c then a divides c — so checking each new element against only the CHAIN'S LAST member is enough. Unsorted, you would have to check it against every member, and the LIS shape would not apply.
What replaces the 'is greater than' test of ordinary LIS?
One predicate swapped and everything else — the table, the parent array, the backward walk — is unchanged. Recognising that the LIS SHAPE is separable from the 'increasing' test is what makes the next two rows free.
The problem asks for the SUBSET, not its size. What does that require?
The same reconstruction technique, reused verbatim on a different predicate. Two units in and the LIS machinery is already being applied rather than derived — which is the point of teaching the pattern rather than the problems.
“Every pair in the subset divides.” A pairwise condition that becomes a chain condition the moment the array is sorted.
Sort first. Divisibility is then transitive along the chain — if a divides b and b divides c then a divides c — so checking each new element against only the chain's LAST member is enough. That is exactly LIS's structure with a different predicate, and the parent-array reconstruction comes along unchanged.
vector<int> largestDivisibleSubset(vector<int>& a) { sort(a.begin(), a.end()); // sorting makes divisibility transitive int n = a.size(), best = 0, at = 0; vector<int> dp(n, 1), parent(n); for (int i = 0; i < n; i++) { parent[i] = i; for (int j = 0; j < i; j++) if (a[i] % a[j] == 0 && dp[j] + 1 > dp[i]) { // the swapped test dp[i] = dp[j] + 1; parent[i] = j; } if (dp[i] > best) { best = dp[i]; at = i; } } vector<int> out; while (parent[at] != at) { out.push_back(a[at]); at = parent[at]; } out.push_back(a[at]); return out; }
def largestDivisibleSubset(a): a = sorted(a) # sorting makes divisibility transitive n = len(a) dp, parent = [1] * n, list(range(n)) best, at = 0, 0 for i in range(n): for j in range(i): if a[i] % a[j] == 0 and dp[j] + 1 > dp[i]: # the swapped test dp[i] = dp[j] + 1 parent[i] = j if dp[i] > best: best, at = dp[i], i out = [] while parent[at] != at: out.append(a[at]); at = parent[at] out.append(a[at]) return out[::-1]
Skipping the sort. Without it, divisibility is not transitive along the chain and you would have to test each candidate against every existing member — the LIS shape simply does not apply, and the answer comes out too large.
The predicate becomes a two-pointer scan
WORDS CHAIN WHEN ONE INSERTION MAKES THE NEXT. WHAT IS THE LONGEST CHAIN?
The words must be sorted before the LIS runs. Sorted by what?
A predecessor is exactly one character shorter, so sorting by length guarantees it has already been processed. Sorting alphabetically breaks that and the chain is built from words that have not been considered yet.
What is the predicate now?
Length alone is not enough — 'bda' is one longer than 'bad' but is not formed by an insertion, because the order must be preserved. The check is a two-pointer scan, and getting it wrong makes the chain too long.
What does this cost compared with plain LIS?
O(n² · L), because each of the n² pairs now runs a two-pointer scan over the characters. Worth stating out loud in an interview: the SHAPE is LIS, and the cost of the predicate is what makes the complexity differ.
Words, and “one insertion makes the next”. A chain condition on strings — LIS again, with the comparison replaced by a scan.
Sort by LENGTH, so every candidate predecessor has already been processed. Then it is the LIS fill with 'is b formed by inserting one character into a' as the predicate. That check is a two-pointer walk, so each of the n² comparisons costs O(L) — the shape is LIS and the predicate is what sets the complexity.
bool isPredecessor(string& a, string& b) { // b is a plus one char if (b.size() != a.size() + 1) return false; int i = 0, j = 0; while (j < (int)b.size()) { if (i < (int)a.size() && a[i] == b[j]) i++; j++; } return i == (int)a.size(); } int longestStrChain(vector<string>& w) { sort(w.begin(), w.end(), [](const string& x, const string& y){ return x.size() < y.size(); }); // sort by LENGTH, not alphabetically int n = w.size(), best = 1; vector<int> dp(n, 1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) if (isPredecessor(w[j], w[i])) dp[i] = max(dp[i], dp[j] + 1); best = max(best, dp[i]); } return best; }
def isPredecessor(a, b): # is b == a plus one character? if len(b) != len(a) + 1: return False i = 0 for ch in b: if i < len(a) and a[i] == ch: i += 1 return i == len(a) def longestStrChain(w): w = sorted(w, key=len) # sort by LENGTH, not alphabetically n = len(w) dp = [1] * n for i in range(n): for j in range(i): if isPredecessor(w[j], w[i]): dp[i] = max(dp[i], dp[j] + 1) return max(dp)
Testing only that the lengths differ by one. 'bda' is one longer than 'bad' and is not formed by an insertion — order must be preserved. The chain comes out longer than it should, on inputs that look fine.
Two LIS runs, joined at every candidate peak
RISE THEN FALL. HOW LONG CAN THAT BE?
A bitonic subsequence rises then falls. How is it computed?
Run the O(n²) LIS forwards into one array and backwards into another. Each index is then a candidate PEAK, and the bitonic length through it is the two values added minus one — the peak counted twice.
Why subtract one when combining the two arrays at index i?
lis[i] includes a[i] and lds[i] includes a[i], so adding them double-counts the peak. An off-by-one that inflates every answer by exactly one — a wrong number that is right-shaped and passes casual inspection.
Must a bitonic subsequence have a strictly rising AND a strictly falling part?
Different judges differ, and the answer changes by more than one. GfG's version permits a monotonic sequence to count; some others require a genuine peak. This is a read-the-statement problem, and the deck flags it rather than picking for you.
“Rises then falls.” Two monotonic halves meeting at a peak — so run the LIS you already have, twice, in opposite directions.
lis[i] is the longest rise ending at i; lds[i] is the longest fall starting at i. Treat every index as a candidate peak: the bitonic length through it is the two added, minus one because the peak itself is in both.
int longestBitonicSubsequence(vector<int>& a) { int n = a.size(); vector<int> lis(n, 1), lds(n, 1); for (int i = 0; i < n; i++) // rising, from the left for (int j = 0; j < i; j++) if (a[j] < a[i]) lis[i] = max(lis[i], lis[j] + 1); for (int i = n - 1; i >= 0; i--) // falling, from the right for (int j = n - 1; j > i; j--) if (a[j] < a[i]) lds[i] = max(lds[i], lds[j] + 1); int best = 0; for (int i = 0; i < n; i++) best = max(best, lis[i] + lds[i] - 1); // -1: the peak counts twice return best; }
def longestBitonicSubsequence(a): n = len(a) lis, lds = [1] * n, [1] * n for i in range(n): # rising, from the left for j in range(i): if a[j] < a[i]: lis[i] = max(lis[i], lis[j] + 1) for i in range(n - 1, -1, -1): # falling, from the right for j in range(n - 1, i, -1): if a[j] < a[i]: lds[i] = max(lds[i], lds[j] + 1) return max(lis[i] + lds[i] - 1 for i in range(n)) # -1: peak counts twice
Forgetting the −1. The peak is counted in both arrays, so every answer comes out exactly one too large — right-shaped, monotonic in the input, and wrong on every single test case.
Counting alongside the optimisation
HOW MANY DIFFERENT SUBSEQUENCES ACHIEVE THE LONGEST LENGTH?
What does the second array alongside dp[] hold?
Two arrays walked together: length and count. Every counting problem in this step has done the same thing — run the optimisation, then carry a tally beside it. What differs is the update rule, which is the next drill.
Extending from j gives a chain LONGER than the best ending at i so far. What happens to cnt[i]?
A longer chain invalidates everything counted so far, so the tally starts again from cnt[j]. Adding instead of replacing is the bug — the count comes out too large while the LENGTH stays perfectly correct, so the failure is invisible in the easy half of the output.
Extending from j gives a chain EXACTLY as long as the best so far. Then?
Equal length means a genuinely different route to the same best, so the counts accumulate. Replace-on-longer, add-on-equal is the whole rule, and mixing the two up is the entire difficulty of this row.
“How many” longest increasing subsequences. Counting alongside an optimisation — the same pairing deck II used, one dimension along.
Carry two arrays: the length ending at i, and how many chains achieve it. When a longer chain arrives, everything counted so far is no longer longest, so the tally is REPLACED. When an equal-length chain arrives, it is a genuinely different route to the same best, so the tallies ADD. Replace-on-longer, add-on-equal is the whole rule.
int findNumberOfLIS(vector<int>& a) { int n = a.size(), best = 0, total = 0; vector<int> dp(n, 1), cnt(n, 1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a[j] >= a[i]) continue; if (dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; cnt[i] = cnt[j]; // LONGER: replace the tally } else if (dp[j] + 1 == dp[i]) { cnt[i] += cnt[j]; // EQUAL: another route, so add } } best = max(best, dp[i]); } for (int i = 0; i < n; i++) if (dp[i] == best) total += cnt[i]; return total; }
def findNumberOfLIS(a): n = len(a) dp, cnt = [1] * n, [1] * n for i in range(n): for j in range(i): if a[j] >= a[i]: continue if dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 cnt[i] = cnt[j] # LONGER: replace the tally elif dp[j] + 1 == dp[i]: cnt[i] += cnt[j] # EQUAL: another route, so add best = max(dp) return sum(c for l, c in zip(dp, cnt) if l == best)
Adding where you should replace. The LENGTH stays perfectly correct, so half the output looks right — only the count is inflated, and only on inputs with more than one optimal chain.
The one genuinely new idea in step 16
MULTIPLY A CHAIN OF MATRICES. WHICH ORDER COSTS LEAST?
The lecturer calls this a new PATTERN, not just a new problem. What is new about it?
Every DP before this chose an ELEMENT — take it or skip it. Partition DP chooses a CUT POINT, recurses on both sides, and combines at the cut. It is the one genuinely new idea in step 16, and he warns it is the hard pattern.
Why does the recursion start at i = 1 rather than i = 0?
n matrices are described by n+1 dimensions, so matrix i is arr[i-1] × arr[i]. The chain of matrices runs 1..n-1 in that array. Getting this indexing wrong is the single most common way MCM goes wrong, and it produces a plausible number.
What is the cost combined AT the split point k?
Both sides collapse to single matrices — one is arr[i-1] × arr[k], the other arr[k] × arr[j] — and multiplying those costs their product of dimensions. Forgetting the combine term entirely is the other classic MCM bug.
Why does k loop over every value from i to j−1 rather than a chosen split?
There is no greedy choice of split, which is exactly why this is a DP. The loop over k is the partition pattern's signature — see a loop over cut points inside a two-index state and you are looking at partition DP.
Matrices with dimensions [10, 20, 30, 40, 30]. Every earlier bench in this step filled a rectangle; this one fills half of one, because f(i, j) only means anything for i ≤ j. The diagonal is the base case, the fill runs by increasing range length, and each cell tries every cut point. There is no local rule for which is best.
“In which order should these be multiplied?” No element to take or skip — you are choosing where to split, which is a different pattern from everything before it.
For a range of matrices, the last multiplication happens at some split k: the left side has collapsed to one matrix, so has the right, and joining them costs the product of three dimensions. There is no local rule for the best k, so you try every one. The state is a RANGE rather than a position, which is what makes the table triangular.
int f(int i, int j, vector<int>& d, vector<vector<int>>& dp) { if (i == j) return 0; // one matrix: nothing to multiply if (dp[i][j] != -1) return dp[i][j]; int best = INT_MAX; for (int k = i; k < j; k++) { // EVERY cut point int cost = f(i, k, d, dp) + f(k+1, j, d, dp) + d[i-1] * d[k] * d[j]; // the COMBINE term best = min(best, cost); } return dp[i][j] = best; }
from functools import lru_cache def mcm(d): n = len(d) - 1 # n matrices, n+1 dimensions @lru_cache(maxsize=None) def f(i, j): if i == j: return 0 # one matrix: nothing to multiply return min(f(i, k) + f(k+1, j) + d[i-1] * d[k] * d[j] # the COMBINE term for k in range(i, j)) # EVERY cut point return f(1, n)
Omitting the d[i−1]·d[k]·d[j] combine term. Splitting becomes free, so the answer is just the sum of the sub-costs — always too small, always plausible, and the recursion structure looks textbook-correct.
The one place in step 16 where the loops run backwards
SAME PROBLEM, TABULATED. WHY IS THAT WORTH ITS OWN LECTURE?
In what order must the two loops run when tabulating MCM?
f(i, j) reads f(i, k) and f(k+1, j) — smaller ranges inside the current one. Only i-down, j-up guarantees those are filled first. This is why the sheet gives the tabulated form its own row: the loop order is genuinely counter-intuitive.
What does the base case become in the tabulated form?
One matrix needs no multiplication, so the diagonal is 0. Every partition DP has this shape: the base is the diagonal, because that is where the range has collapsed to a single item.
Why is tabulating this worth a separate nine-minute lecture at all?
Same O(n³) either way. The lecture exists because every earlier tabulation in this step ran its loops upward and this one does not — and the deck ships it as a diff so the reversal is the only thing on screen.
The same problem, tabulated. The sheet gives it a row of its own because partition DP is the one place in step 16 where the loop order is not the usual one.
f(i, j) reads f(i, k) and f(k+1, j) — ranges strictly INSIDE itself. So those must already be filled, which forces i to run downward while j runs upward. Every earlier tabulation in this step ran both loops upward; this is the exception, and it is genuinely easy to get wrong.
int mcm(vector<int>& d) { int n = d.size() - 1; // n matrices, n+1 dimensions vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0)); for (int i = n; i >= 1; i--) // i DOWNWARD for (int j = i + 1; j <= n; j++) { // j UPWARD dp[i][j] = INT_MAX; for (int k = i; k < j; k++) { // EVERY cut point int cost = dp[i][k] + dp[k+1][j] + d[i-1] * d[k] * d[j]; // the COMBINE term dp[i][j] = min(dp[i][j], cost); } } return dp[1][n]; }
def mcm(d): n = len(d) - 1 # n matrices, n+1 dimensions dp = [[0] * (n + 1) for _ in range(n + 1)] for i in range(n, 0, -1): # i DOWNWARD for j in range(i + 1, n + 1): # j UPWARD dp[i][j] = min(dp[i][k] + dp[k+1][j] + d[i-1] * d[k] * d[j] # the COMBINE term for k in range(i, j)) # EVERY cut point return dp[1][n]
Running both loops upward out of habit. The cells it reads are still zero, so the answer comes out far too small with no error and no crash — the same failure as a missing combine term, from a different cause.
Sentinels that give every range a length
CUT A STICK AT GIVEN POSITIONS. EACH CUT COSTS THE PIECE'S LENGTH.
Two things are done to the cuts array before the DP runs. Which?
Sorting makes the cuts within a range contiguous; the sentinels give every range a concrete left and right boundary so the cost of a cut is a simple subtraction. Skip either and the recurrence cannot be written cleanly.
What is the cost of making a cut at position k inside the range (i, j)?
The cost is the CURRENT stick's length, which the sentinels make readable as the gap between the boundaries just outside the range. This is why they were added — without them the boundary ranges have no length to read.
Why does the order of cuts matter at all — why is this not just a sum?
Cut early and you pay for a long stick; cut late and the piece is already short. Different orders give genuinely different totals, which is what makes it an optimisation — and it is the same reason Burst Balloons needs a table.
“Each cut costs the length of the piece being cut.” A cost that depends on what is left — so the ORDER matters, and order-dependence means partition DP.
Sort the cut positions and add 0 and n as sentinels. A range of cuts then has a concrete left and right boundary, so the cost of cutting anywhere inside it is just the distance between those boundaries. Choose which cut in the range happens FIRST, pay that length, and both sides become independent ranges.
int minCost(int n, vector<int>& cuts) { cuts.push_back(0); cuts.push_back(n); // SENTINELS: every range gets ends sort(cuts.begin(), cuts.end()); int m = cuts.size(); vector<vector<int>> dp(m + 1, vector<int>(m + 1, 0)); for (int i = m - 2; i >= 1; i--) for (int j = i; j <= m - 2; j++) { int best = INT_MAX; for (int k = i; k <= j; k++) best = min(best, dp[i][k-1] + dp[k+1][j] + cuts[j+1] - cuts[i-1]); // the piece's LENGTH dp[i][j] = best; } return dp[1][m - 2]; }
def minCost(n, cuts): cuts = sorted(cuts + [0, n]) # SENTINELS: every range gets ends m = len(cuts) dp = [[0] * (m + 1) for _ in range(m + 1)] for i in range(m - 2, 0, -1): for j in range(i, m - 1): dp[i][j] = min(dp[i][k-1] + dp[k+1][j] + cuts[j+1] - cuts[i-1] # the piece's LENGTH for k in range(i, j + 1)) return dp[1][m - 2]
Skipping the sentinels. Without a boundary just outside the range there is nothing to subtract, and the boundary ranges have no length at all — so the recurrence cannot even be written, and improvised substitutes are wrong at the edges.
Reversing the question so the sides stay independent
BURST BALLOONS FOR COINS. WHICH ORDER MAXIMISES WHAT YOU COLLECT?
Why can this not be solved by asking which balloon to burst FIRST?
Burst a middle balloon first and the two sides become adjacent — so they are no longer independent subproblems and the recursion cannot split. This is the obstacle the whole lecture is built around.
What is the fix?
If k is burst LAST in a range, its neighbours at that moment are exactly the range's boundaries — which are fixed and known. The two sides become independent again, and the standard partition recurrence applies. Reversing the question is the entire trick.
What does the gain at the split k evaluate to?
Because k is burst last, everything strictly inside the range is already gone and its neighbours are the cells just OUTSIDE it. Using the immediate neighbours is the reflex, and it is what the reversal exists to avoid.
An operation that changes its neighbours. That is the tell for reversing the question — and it is why the obvious recursion does not work.
Bursting a middle balloon makes its neighbours adjacent, so the two sides are no longer independent and cannot be recursed on. Ask instead which balloon is burst LAST in a range: at that moment everything else inside is gone, so its neighbours are exactly the range's fixed boundaries. The sides become independent again and the standard partition recurrence applies.
int maxCoins(vector<int>& nums) { vector<int> a; a.push_back(1); for (int x : nums) a.push_back(x); a.push_back(1); // sentinels of 1 at both ends int n = a.size(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int i = n - 2; i >= 1; i--) for (int j = i; j <= n - 2; j++) { int best = 0; for (int k = i; k <= j; k++) // k is burst LAST in this range best = max(best, a[i-1] * a[k] * a[j+1] + dp[i][k-1] + dp[k+1][j]); dp[i][j] = best; } return dp[1][n - 2]; }
def maxCoins(nums): a = [1] + list(nums) + [1] # sentinels of 1 at both ends n = len(a) dp = [[0] * n for _ in range(n)] for i in range(n - 2, 0, -1): for j in range(i, n - 1): dp[i][j] = max(a[i-1] * a[k] * a[j+1] # k is burst LAST + dp[i][k-1] + dp[k+1][j] for k in range(i, j + 1)) return dp[1][n - 2]
Using the immediate neighbours a[k−1] and a[k+1] in the gain. Because k is burst LAST, everything strictly inside the range has already gone — its neighbours are the cells outside it. Using the immediate ones is the reflex the reversal exists to avoid.
A partition where the counts multiply instead of adding
HOW MANY WAYS CAN YOU PARENTHESISE THIS EXPRESSION SO IT EVALUATES TO TRUE?
What does the state carry beyond the two range endpoints?
A third index for the required outcome, because an AND needs both sides TRUE while an OR needs either — so you must be able to ask for FALSE counts too. Partition DP with one extra bit of state, and that bit is the whole problem.
The split point k in this problem lands on what?
k steps by two, landing only on operators, so each side is a well-formed expression. Splitting on operands produces fragments that cannot be evaluated — which is what makes this partition variant look harder than it is.
Counting ways for an AND to be TRUE combines the sides how?
Every left parenthesisation pairs with every right one, so counts MULTIPLY. Every earlier counting problem in step 16 added its branches, because they were alternatives; here they are simultaneous. Adding is the natural reflex and it is wrong.
“In how many ways can it be parenthesised so it evaluates to true?” Partition DP with a third index — and the one place counts multiply rather than add.
Split at an operator so both sides are whole expressions. An AND is true only when both sides are, so its count is leftTrue × rightTrue — every left parenthesisation pairs with every right one. Because an OR needs either side true, you also have to be able to ask for FALSE counts, which is what the third state index is for.
int countWays(string& s) { int n = s.size(); const int MOD = 1003; // dp[i][j][isTrue] - the third index is the required OUTCOME vector<vector<array<long long,2>>> dp(n, vector<array<long long,2>>(n, {0,0})); for (int i = 0; i < n; i += 2) { // operands sit at even indices dp[i][i][1] = (s[i] == 'T'); dp[i][i][0] = (s[i] == 'F'); } for (int i = n - 1; i >= 0; i -= 2) for (int j = i + 2; j < n; j += 2) for (int t = 0; t < 2; t++) { long long ways = 0; for (int k = i + 1; k < j; k += 2) { // k lands on OPERATORS long long lT = dp[i][k-1][1], lF = dp[i][k-1][0]; long long rT = dp[k+1][j][1], rF = dp[k+1][j][0]; if (s[k] == '&') ways += t ? lT*rT : lT*rF + lF*rT + lF*rF; // MULTIPLY else if (s[k] == '|') ways += t ? lT*rT + lT*rF + lF*rT : lF*rF; else ways += t ? lT*rF + lF*rT : lT*rT + lF*rF; } dp[i][j][t] = ways % MOD; } return (int)dp[0][n-1][1]; }
def countWays(s): n = len(s) MOD = 1003 from functools import lru_cache @lru_cache(maxsize=None) def f(i, j, want): # want: the required OUTCOME if i == j: return int((s[i] == 'T') == want) ways = 0 for k in range(i + 1, j, 2): # k lands on OPERATORS only lT, lF = f(i, k-1, True), f(i, k-1, False) rT, rF = f(k+1, j, True), f(k+1, j, False) if s[k] == '&': ways += lT*rT if want else lT*rF + lF*rT + lF*rF # MULTIPLY elif s[k] == '|': ways += (lT*rT + lT*rF + lF*rT) if want else lF*rF else: ways += (lT*rF + lF*rT) if want else lT*rT + lF*rF return ways % MOD return f(0, n - 1, True)
Adding the two sides' counts instead of multiplying them. Every earlier counting DP in step 16 added, because its branches were alternatives; here both sides happen at once and their choices compose. The number comes out far too small.
Cutting from the front instead of the middle
SPLIT THE STRING SO EVERY PIECE IS A PALINDROME. WHAT IS THE FEWEST CUTS?
The lecture calls this a DIFFERENT form of partition from MCM. What changes?
Front partition: take a valid prefix, pay for it, recurse on what is left. One index instead of two, so it is O(n²) rather than O(n³) — and it is the shape of most partition problems that are not MCM.
The recursion returns the number of CUTS, but the base case is subtle. Why?
Every recursive call charges 1 for the cut it makes, including the last piece — which needs no cut after it. Returning −1 at the end cancels that overcharge exactly. An answer one too large is exactly what you get without it.
The naive version checks isPalindrome inside the loop. What does precomputing it buy?
A palindrome table filled once in O(n²) makes every check O(1), so the whole thing is O(n²). This is the standard follow-up after you produce the working version, and it is worth volunteering before being asked.
“Partition the string so every piece is a palindrome, minimise the cuts.” A different partition shape: you cut from the FRONT and only the remainder recurses.
Take a prefix that is a palindrome, charge one cut, and recurse on what is left. Only one side recurses, so the state is a single position rather than a range — which makes this O(n²) rather than O(n³). The base case returns −1 to cancel the cut charged for the final piece, which needs no cut after it.
int minCut(string s) { int n = s.size(); vector<vector<bool>> pal(n, vector<bool>(n, false)); for (int i = n - 1; i >= 0; i--) // precompute: O(n^3) -> O(n^2) for (int j = i; j < n; j++) pal[i][j] = (s[i] == s[j]) && (j - i < 2 || pal[i+1][j-1]); vector<int> dp(n + 1, 0); dp[n] = -1; // -1 cancels the last piece's cut for (int i = n - 1; i >= 0; i--) { int best = INT_MAX; for (int j = i; j < n; j++) // FRONT partition: take a prefix if (pal[i][j]) best = min(best, 1 + dp[j+1]); dp[i] = best; } return dp[0]; }
def minCut(s): n = len(s) pal = [[False] * n for _ in range(n)] for i in range(n - 1, -1, -1): # precompute: O(n^3) -> O(n^2) for j in range(i, n): pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i+1][j-1]) dp = [0] * (n + 1) dp[n] = -1 # -1 cancels the last piece's cut for i in range(n - 1, -1, -1): dp[i] = min(1 + dp[j+1] # FRONT partition: take a prefix for j in range(i, n) if pal[i][j]) return dp[0]
Returning 0 from the base case. Every recursive call charges 1, including the one that consumes the final piece — so the answer comes out exactly one too high on every input, which is the easiest kind of wrong to ship.
Front partition with a bound on the piece
SPLIT INTO PIECES OF AT MOST k, EACH BECOMING ITS MAXIMUM. MAXIMISE THE SUM.
Each subarray may be at most k long and becomes k copies of its maximum. What does the front-partition loop do?
The loop is bounded by k rather than by n, which is what makes this O(n·k). Same front-partition shape as palindrome partitioning, with a cap on how far the first piece may extend.
How is the running maximum handled inside that loop?
Extending the piece by one element can only raise the maximum, so carrying it costs nothing. Re-scanning makes it O(n·k²) — the same 'the loop already has what you need' observation that keeps MCM's combine step cheap.
The value contributed by a piece of length L with maximum m is what?
The statement replaces every element of the subarray with the maximum, so a piece of length L is worth L × m. Reading it as m alone makes long pieces worthless and biases every answer toward tiny partitions.
“Subarrays of at most k, each replaced by its maximum.” Front partition again, with a bound on how far the first piece may reach.
Same shape as the previous problem — take a prefix, pay for it, recurse on the rest — but the prefix may only be up to k long, so the loop is bounded by k rather than by n. The maximum of the growing piece is carried as the loop extends, because adding an element can only raise it.
int maxSumAfterPartitioning(vector<int>& a, int k) { int n = a.size(); vector<int> dp(n + 1, 0); for (int i = n - 1; i >= 0; i--) { int mx = 0, best = 0; for (int L = 1; L <= k && i + L <= n; L++) { mx = max(mx, a[i + L - 1]); // carried, never re-scanned best = max(best, L * mx + dp[i + L]); // a piece is worth L * max } dp[i] = best; } return dp[0]; }
def maxSumAfterPartitioning(a, k): n = len(a) dp = [0] * (n + 1) for i in range(n - 1, -1, -1): mx = best = 0 for L in range(1, min(k, n - i) + 1): mx = max(mx, a[i + L - 1]) # carried, never re-scanned best = max(best, L * mx + dp[i + L]) # a piece is worth L * max dp[i] = best return dp[0]
Valuing a piece at its maximum rather than at length × maximum. Every element of the subarray becomes the maximum, so a piece of length L is worth L times it — reading it as m alone makes long pieces worthless and biases every answer toward tiny partitions.
A DP that hands its state to a stack
LARGEST ALL-ONES RECTANGLE IN A BINARY MATRIX.
A binary matrix, largest all-ones rectangle. How is it reduced?
Row by row, a cell's height is the run of consecutive 1s ending at it vertically — reset to 0 on a 0. Every row is then a histogram, and the answer is the best largest-rectangle-in-a-histogram over all n of them.
What solves the histogram half?
Largest rectangle in a histogram is the classic monotonic-stack problem. He says out loud why a stack problem sits in a DP playlist: the carried heights are the remembered state, and the stack is what runs on top of them.
What is the complexity?
n rows, each O(m) to build and O(m) to run the stack over. Optimal, and the reason the reduction is worth knowing rather than just the brute force over all rectangle corners.
A binary matrix and “largest rectangle”. The sheet files it under DP, and the DP part is smaller than it looks — most of the work is a stack.
Walk the matrix row by row, carrying for each column the run of 1s ending at that row — reset to 0 on a 0. Every row is then a histogram, and the answer is the best 'largest rectangle in a histogram' over all n of them. The carried heights are the remembered state; the monotonic stack is what runs on top.
int largestRectangleArea(vector<int>& h) { int n = h.size(), best = 0; stack<int> st; // MONOTONIC stack, from step 09 for (int i = 0; i <= n; i++) { int cur = (i == n) ? 0 : h[i]; while (!st.empty() && h[st.top()] >= cur) { int height = h[st.top()]; st.pop(); int left = st.empty() ? -1 : st.top(); best = max(best, height * (i - left - 1)); } st.push(i); } return best; } int maximalRectangle(vector<vector<char>>& g) { int n = g.size(), m = g[0].size(), best = 0; vector<int> heights(m, 0); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) // the carried heights ARE the DP heights[j] = (g[i][j] == '1') ? heights[j] + 1 : 0; best = max(best, largestRectangleArea(heights)); } return best; }
def largestRectangleArea(h): best, st = 0, [] # MONOTONIC stack, from step 09 for i in range(len(h) + 1): cur = 0 if i == len(h) else h[i] while st and h[st[-1]] >= cur: height = h[st.pop()] left = st[-1] if st else -1 best = max(best, height * (i - left - 1)) st.append(i) return best def maximalRectangle(g): if not g: return 0 m, best = len(g[0]), 0 heights = [0] * m for row in g: for j in range(m): # the carried heights ARE the DP heights[j] = heights[j] + 1 if row[j] == '1' else 0 best = max(best, largestRectangleArea(heights)) return best
Rebuilding the heights from scratch for each row. It is O(n·m) per row and turns the whole thing into O(n²·m) — the carried heights ARE the dynamic programming here, and recomputing them throws away the only DP in the problem.
Three neighbours, one min, and a sum at the end
HOW MANY ALL-ONES SQUARE SUBMATRICES ARE THERE ALTOGETHER?
dp[i][j] is the side of the largest all-ones square with its bottom-right corner at (i, j). How is it computed?
A square of side s here needs squares of side s−1 at all three neighbours — the MIN is what enforces 'all three', because the weakest one limits you. Taking the max would claim squares that contain a zero.
The question asks for the COUNT of all square submatrices. How does the table answer it?
A cell holding 3 means squares of side 1, 2 AND 3 all end there — three of them. So the total is the sum of the whole table. Counting non-zero cells instead counts only the 1×1 squares and undercounts badly.
This is the only EASY row in the deck. What makes it easy after seven partition problems?
It is a grid DP from deck I wearing new clothes — read three neighbours, take a min, add one. After Burst Balloons and MCM the sheet is ending step 16 gently on purpose, and the deck ends on it too.
Each cell is the side of the largest all-ones square with its bottom-right corner there, 1 + min of up, left and diagonal. The min is what enforces all three. And the answer is the sum of every cell, because a cell holding 3 contains squares of side 1, 2 and 3.
A binary matrix and “count all square submatrices”. No partitioning, no stack — three neighbours and a min, which is deck I's grid DP in new clothes.
Let dp[i][j] be the side of the largest all-ones square whose bottom-right corner is at (i, j). A square of side s there needs squares of side s−1 at the cells above, left and diagonally up-left — so the MIN of those three, plus one, is what this corner supports. And a cell holding 3 contains squares of side 1, 2 and 3, so the total count is the sum of the whole table.
int countSquares(vector<vector<int>>& g) { int n = g.size(), m = g[0].size(), total = 0; vector<vector<int>> dp(n, vector<int>(m, 0)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { if (!g[i][j]) dp[i][j] = 0; else if (!i || !j) dp[i][j] = 1; // on an edge: 1x1 only else dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}); total += dp[i][j]; // a cell holding s contains s squares } return total; }
def countSquares(g): n, m, total = len(g), len(g[0]), 0 dp = [[0] * m for _ in range(n)] for i in range(n): for j in range(m): if not g[i][j]: dp[i][j] = 0 elif i == 0 or j == 0: dp[i][j] = 1 # on an edge: 1x1 only else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) total += dp[i][j] # a cell holding s contains s squares return total
Counting the cells that are non-zero, or reading the table's maximum. A cell of value s contains s squares, so the answer is the SUM — counting non-zero cells returns only the number of 1×1 squares, which is a plausible undercount.
A partition DP's base case sits where in the table?
The diagonal. f(i, i) is a range of one — one matrix costs nothing to multiply, one character is already a palindrome. Every partition problem has this shape, and the triangular table is what makes it visible.
Tabulating a partition DP, which way must the loops run?
i down, j up. f(i, j) reads ranges INSIDE itself, so those must already exist. This is the only place in step 16 where the loop order is reversed, which is why the sheet gives the tabulated MCM its own row.
Front partition — palindrome partitioning, partition array for maximum sum — differs from MCM how?
Only the right side recurses. The prefix is finished and paid for, so the state is a single position — O(n²) rather than O(n³). Most partition problems that are not MCM have this shape, and recognising which you have decides the complexity before you write anything.
Counting parenthesisations that evaluate to true, an AND node combines its sides by…
Multiply. Every counting problem before this one ADDED, because its branches were alternatives — pick or skip, one or the other. Here both sides happen at once and their choices compose, so the counts multiply. Adding is the reflex and it is wrong.
LIS by binary search: what is in the maintained array?
Smallest tails. A smaller tail is never worse, which keeps the array sorted and makes binary search legal. Its LENGTH is the answer; its contents may never have co-occurred as a subsequence, so printing it is the classic misuse.
Counting all-ones square submatrices, the answer is…
Sum the table. A cell holding 3 means squares of side 1, 2 and 3 all end there. Counting non-zero cells counts only the 1×1s; reading the corner answers a different question entirely — the same 'where does the answer live' problem this step keeps posing.
Partition DP fails quietly. A missing combine term, a loop running the wrong way, a count added where it should have multiplied — every one of these returns a number, and the recursion above it looks exactly like the textbook.
dp[i][k] + dp[k+1][j] with nothing added for joining them. Splitting becomes free, the answer is always too small, and the recursion looks textbook-perfect.
Bursting a middle balloon joins its neighbours, so the halves are not independent and the recurrence is simply invalid. Ask which is burst LAST instead.
f(i, j) reads ranges inside itself, so i must run DOWNWARD. Upward reads cells that are still zero and produces a confident, much-too-small answer.
In boolean parenthesisation an AND's sides happen together, so their counts compose multiplicatively. Every earlier counting DP added, which is exactly why this gets missed.
Overwriting tails leaves an array of the right LENGTH whose contents may never have formed a subsequence. The number is right and the sequence is fiction.
Each cell is the run ENDING there, so the answer is the maximum over the array. Reading the last cell answers 'the longest run that must include the final element'.
Sixteen rows and the last page of step 16. The top seven are LIS with one thing swapped each time; the middle seven are partition DP; the last two are grids.
Seven problems that carried the last thing you took — and one that threw the table away for a binary search on tails. Then the pattern that is different in kind: stop choosing elements, choose a split, solve both sides, and pay something at the join. Matrix chains, sticks, balloons burst in reverse, boolean expressions whose counts multiply, and two front partitions where only the remainder recurses. That completes step 16 — fifty-five rows, fifty-six lectures, four decks. Every one of them was the same three sentences: express it by index, do everything possible there, then take the max, the min or the sum.
Deck 4 of 4, and the last of step 16. Lectures DP 41-56 of 56, sixteen against sixteen sheet rows. With this deck the playlist is fully used and all 55 rows of the sheet have a slide. Every drill cites its lecture transcript; every bench fills in numbers the build re-derived; and every code listing was executed against the judge's own examples before it shipped.
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.