Every problem in this deck is the same two-line recurrence: take this element and reduce the target, or skip it and don't. What changes is only what you do with the two branches — OR them for reachability, ADD them to count, MIN or MAX them to optimise. Eleven lectures, one recurrence, and a second index that is no longer a position but a sum you still owe.
This is not a list of problems. It is 11 learning units, and every one runs the same four beats. Go in order and the problems stop feeling random.
ASSUMEDDeck I of this step — the four forms of a recurrence, and pick / not-pick from problem #05. Every recurrence here is pick / not-pick with a RUNNING TARGET as the second index instead of a position. Deck I ended on its hardest slide — two movers on one grid, three indices. This one opens easier on purpose and does not build on that: the last unit you actually need is #05, pick / not-pick over a single index. If unit 1 feels like a step backwards, that is the shape of the step, not a lecture you missed.
11 PROBLEMS · EVERY ONE LINKS TO A JUDGE TO SOLVE
Every problem in this deck picks or skips an element and reduces a target. What differs is only what you do with the two branches — and which of these six phrasings the statement uses tells you which. The recurrence is never the hard part.
you only need to know whether it can be done, so the two branches are OR-ed
REACHABILITY · boolean table, memo sentinel is −1O(n·T)pick and not-pick are disjoint, so their counts add — and a zero doubles them
COUNTING · same table, ADD the branchesO(n·T)optimise over the same two branches, and make an impossible state unattractive
KNAPSACK · MIN or MAX, ±∞ for impossibleO(n·W)the item is still available after you take it, so the take branch does not move on
UNBOUNDED · take stays at the same indexO(n·W)not new problems — algebra turns each into a subset sum for one specific target
REDUCTION · solve, then reuseO(n·T)check it against a counterexample before writing it; on coins {9,6,5,1} it loses
STOP · the obvious choice is not always optimal—The cost of every DP here is (number of states) × (work per state), and the state is (index, target). So the TARGET's magnitude decides whether a table is possible at all — which is why a huge target means the answer is not DP, however much the statement looks like it.
This is the one deck where a bound on the VALUES matters more than a bound on n: 20 items with a target of 10⁹ is not a knapsack, it is meet-in-the-middle.
In deck I the second index of a 2D table was a position in a grid. In this deck it is something else. What?
A debt, not a place. Taking an element pays part of the target off; skipping leaves it owed. Once the second index is a number rather than a coordinate, subset sum, knapsack, coin change and rod cutting are visibly the same table — which is the claim this whole deck is built to make.
A reachability DP returns true or false. Why must its memo table hold int rather than bool?
Three states, two answers. The memo needs true, false and unvisited; the first two are the answer, so the sentinel must be a third value. It is the one mechanical difference between a boolean DP and a numeric one, and it is why these tables are int filled with −1.
Counting subsets that sum to a target. It returns the right answer on most inputs and silently halves it on some. Which line?
int f(int i, int t, vector<int>& a, vector<vector<int>>& dp){ if(i == 0) return (t == a[0] || t == 0) ? 1 : 0; if(dp[i][t] != -1) return dp[i][t]; int notPick = f(i-1, t, a, dp); int pick = (a[i] <= t) ? f(i-1, t - a[i], a, dp) : 0; return dp[i][t] = notPick + pick; }
A zero can be taken or skipped. If a[0] == 0 and t == 0, both the empty subset and {0} are valid, so the base case owes 2. It never fires on arrays of positive integers — which is why the earlier lecture's constraints hid it and the later one's exposed it.
Coins {9, 6, 5, 1} and a target of 11. Greedy takes the largest coin it can, repeatedly. Is it right here?
Greedy takes the 9 and is then stuck paying 2 with two 1s. Taking no large coin at all gives 6 + 5. A coin of value 1 guarantees an answer EXISTS, never that greedy finds the best one. These are the lecture's own denominations, and unit 07 fills the table beside greedy's run.
Eleven lectures, 4h 46m. Units 01 to 05 build one table and change one operator at a time; unit 06 names the problem all of them are — 0/1 knapsack, which the sheet has no row for — and units 07 to 11 are that problem with unlimited supply. Unit 07 carries two rows on purpose: one where greedy is right and one where it is wrong.
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.
A subset-sum table, where the second index is the sum you still owe
CAN ANY SUBSET OF THIS ARRAY ADD UP TO EXACTLY THIS TARGET?
The lecture opens by defining a subsequence, and stresses one word. Which definition is right?
Contiguous or non-contiguous — he says 'very important' on exactly that word. It matters because it is what licenses pick / not-pick: if subsequences had to be contiguous you would be choosing a window, not choosing per element.
The answer at each state is a boolean. Why can the memo table NOT be a plain array of booleans?
A memo needs three states: true, false, and unvisited. Two of them are the answer, so the sentinel has to be a third value — which is why the table is int filled with -1 even though the function returns a bool. This is the one place a boolean DP differs mechanically from a numeric one.
The second index of the table is the target. What does taking an element do to it?
The second index stops being a position and becomes what you still owe. Taking an element pays part of the debt; skipping leaves it. Once that clicks, every remaining problem in this deck is the same table with a different operator over the two branches.
[2, 3, 5], target 8. Rows are how much of the array you may use; columns are what you still owe. Every cell asks one question. Can this prefix make this sum, and answers it by OR-ing two cells in the row above: skip me, or pay me off the target. Same table you filled for a grid, indexed by a debt.
“Is there a subset that sums to…” — you are asked only whether it can be done, not how many ways or how cheaply. That makes the answer a boolean and the two branches an OR.
At every element there are exactly two futures: take it, which pays part of the target off, or skip it, which does not. The target is therefore not a position but a DEBT, and the table is indexed by how much of it is still owed. Every other problem in this deck is this table with a different operator.
bool subsetSum(vector<int>& a, int T) { int n = a.size(); vector<bool> prev(T + 1, false), cur(T + 1, false); prev[0] = true; // empty subset pays 0 if (a[0] <= T) prev[a[0]] = true; for (int i = 1; i < n; i++) { cur[0] = true; for (int t = 1; t <= T; t++) { bool notPick = prev[t]; bool pick = (a[i] <= t) ? prev[t - a[i]] : false; cur[t] = notPick || pick; // OR: reachable at all? } prev = cur; } return prev[T]; }
def subsetSum(a, T): prev = [False] * (T + 1) prev[0] = True # empty subset pays 0 if a[0] <= T: prev[a[0]] = True for i in range(1, len(a)): cur = [False] * (T + 1) cur[0] = True for t in range(1, T + 1): pick = prev[t - a[i]] if a[i] <= t else False cur[t] = prev[t] or pick # OR: reachable at all? prev = cur return prev[T]
Memoizing into a vector<vector<bool>>. True and false are both answers, so there is no value left to mean 'not computed yet' — every lookup either recomputes or returns a stale false. The answer stays right and the runtime stays exponential.
An equal partition is a subset sum for half the total
CAN THIS ARRAY BE SPLIT INTO TWO PARTS WITH THE SAME SUM?
Before any DP runs, one cheap check settles a large fraction of inputs. What is it?
Two subsets of equal sum each hold total/2. If the total is odd there is no such integer and the answer is false with no table at all. Reaching for the recurrence before the parity check is the giveaway that the reduction was never really understood.
Once the sum is even, what is left to compute?
It is problem #01 with one specific target. The whole lecture is nine minutes because there is no new recurrence in it — this is the deck's first pure reduction, and recognising a solved problem underneath a new statement is the skill being drilled.
Array [1, 5, 11, 5]. Does an equal partition exist?
Total is 22, half is 11, and {11} reaches it exactly. The tempting wrong answer is the last one: {1,11} is 12 and {5,5} is 10, which are not equal — a reminder that the check is 'does SOME subset hit total/2', not 'can I eyeball two groups that look close'.
“Two subsets with equal sum.” Equal halves of a fixed total is a target in disguise — and one cheap arithmetic check settles a large share of inputs before any table exists.
If the array splits into two equal halves, each sums to total/2. So the question is only whether SOME subset reaches total/2 — which is the previous problem with one specific target. An odd total makes total/2 a non-integer, so the answer is false immediately.
bool canPartition(vector<int>& a) { int total = accumulate(a.begin(), a.end(), 0); if (total % 2) return false; // odd total: no table needed return subsetSum(a, total / 2); // problem #01, one target }
def canPartition(a): total = sum(a) if total % 2: return False # odd total: no table needed return subsetSum(a, total // 2) # problem #01, one target
Reaching for the recurrence before the parity check. It is not a performance problem — it is a sign the reduction was never seen, and the same reflex will miss the guards on problem #05 where skipping them produces a wrong answer rather than a slow one.
Reading a minimum out of a table you already filled
SPLIT THE ARRAY IN TWO SO THE DIFFERENCE OF THE SUMS IS AS SMALL AS POSSIBLE.
The table is the same subset-sum table. What do you do with its LAST ROW to get the answer?
The last row says which sums a subset can reach. If one part sums to s, the other is total − s, so the gap is |total − 2s| — scan the row and take the best. The table was never rebuilt; only the question asked of it changed.
The dp array's second dimension is declared with size total + 1. What breaks if it is total?
Targets run 0 to total INCLUSIVE, so there are total + 1 of them. It is the same off-by-one as deck I's n+1, one dimension over, and the lecture stops on it for exactly that reason.
Array [1, 6, 11, 5], total 23. What is the minimum achievable difference?
{1, 5, 6} is 12 and {11} is 11, so the gap is 1. With an odd total, 0 is impossible — which is the parity check from the previous unit reappearing as a sanity bound rather than as an early exit.
“Minimum absolute difference between the two parts.” An optimisation over every possible split — but the split is still just a subset, so the table does not change at all.
Fill the ordinary subset-sum table over targets 0..total. Its last row tells you every sum a subset can reach. If one side reaches s the other must be total − s, so the gap is |total − 2s| — scan the row and keep the best. The DP answered a reachability question; the minimisation happens afterwards, in a loop.
int minSubsetSumDifference(vector<int>& a) { int n = a.size(), total = accumulate(a.begin(), a.end(), 0); vector<bool> prev(total + 1, false), cur(total + 1, false); prev[0] = true; if (a[0] <= total) prev[a[0]] = true; for (int i = 1; i < n; i++) { cur[0] = true; for (int t = 1; t <= total; t++) cur[t] = prev[t] || (a[i] <= t ? prev[t - a[i]] : false); prev = cur; } int best = INT_MAX; // now just READ the last row for (int s = 0; s <= total / 2; s++) if (prev[s]) best = min(best, abs(total - 2 * s)); return best; }
def minSubsetSumDifference(a): total = sum(a) prev = [False] * (total + 1) prev[0] = True if a[0] <= total: prev[a[0]] = True for i in range(1, len(a)): cur = [False] * (total + 1) cur[0] = True for t in range(1, total + 1): cur[t] = prev[t] or (prev[t - a[i]] if a[i] <= t else False) prev = cur return min(abs(total - 2 * s) # now just READ the last row for s in range(total // 2 + 1) if prev[s])
Sizing the table `total` instead of `total + 1`. The sum `total` itself is a legal, reachable state — take everything — so the last column is a real answer, not padding. Same off-by-one as deck I's n+1, one dimension along.
Counting instead of checking — the same cells, added
HOW MANY DIFFERENT SUBSETS ADD UP TO EXACTLY K?
Reachability OR-ed the two branches. What does counting do with them?
Pick and not-pick partition the possibilities — no subset both takes and skips an element — so their counts are disjoint and simply add. Identical recursion, one operator different: that is the deck's whole thesis in a single line.
The lecture admits an error in DP 14 and fixes it here. What was missing?
The base case writes at index a[0], and if a[0] is bigger than the declared target the write runs off the end — a runtime error he says he missed in the earlier lecture. Worth knowing both because it is a real bug and because it shows the base case indexes the table just as the loop does.
The constraints are stressed as POSITIVE integers. What goes wrong the moment a zero is allowed?
A zero costs nothing, so taking it and skipping it are two DIFFERENT subsets with the same sum. The base case that returns 1 has to return 2 when a[0] is 0. Harmless when checking reachability, quietly halving your answer when counting.
[1, 2, 2, 3], target 3. Identical recursion, identical table, identical pair of source cells. The two branches are added instead of OR-ed. Watch the base row: a zero in the array would make it 2 rather than 1, which is harmless when checking and halves your answer when counting.
“How many subsets…” rather than “is there a subset…”. One word changes, and only the operator joining the two branches changes with it.
Pick and not-pick can never produce the same subset — one contains a[i] and the other does not — so the two counts are disjoint and simply add. Everything else, the state, the sources, the loop, is identical to problem #01. The one genuinely new hazard is a zero: it costs nothing, so taking it and skipping it are two different subsets with the same sum.
int countSubsets(vector<int>& a, int K) { int n = a.size(); vector<int> prev(K + 1, 0), cur(K + 1, 0); prev[0] = (a[0] == 0) ? 2 : 1; // a zero is in OR out: two subsets if (a[0] != 0 && a[0] <= K) prev[a[0]] = 1; for (int i = 1; i < n; i++) { for (int t = 0; t <= K; t++) { int notPick = prev[t]; int pick = (a[i] <= t) ? prev[t - a[i]] : 0; cur[t] = notPick + pick; // ADD: the branches are disjoint } prev = cur; } return prev[K]; }
def countSubsets(a, K): prev = [0] * (K + 1) prev[0] = 2 if a[0] == 0 else 1 # a zero is in OR out: two subsets if a[0] != 0 and a[0] <= K: prev[a[0]] = 1 for i in range(1, len(a)): cur = [0] * (K + 1) for t in range(K + 1): pick = prev[t - a[i]] if a[i] <= t else 0 cur[t] = prev[t] + pick # ADD: the branches are disjoint prev = cur return prev[K]
Assuming the base case returns 1. If a[0] is 0 there are TWO subsets summing to zero — {} and {0} — so it returns 2. On arrays of positive integers the bug never fires, which is exactly why it survives until a later problem loosens the constraints and halves your answer.
Algebra first, then a count you have already written
HOW MANY WAYS ARE THERE TO SPLIT THE ARRAY SO THE SUMS DIFFER BY EXACTLY D?
Partitions into S1 and S2 with S1 − S2 = D. What target does this reduce to counting subsets for?
S1 + S2 = total and S1 − S2 = D, so S2 = (total − D)/2. Count the subsets summing to that and you have counted the partitions. Two lines of algebra replace an entirely new recurrence — and this is also what the next lecture reduces to.
Two guards are needed on (total − D) before the DP runs. Which pair?
Negative means no such split exists; odd means the target is not an integer. Both return 0 immediately. Skip them and you either index the table with a negative number or silently truncate a fraction — a wrong count rather than a crash.
The lecture says the previous solution 'failed' on a test and explains why. What was the cause?
The earlier problem promised elements ≥ 1, so the zero case never arose; here the constraints allow 0 and each zero doubles the count. It is the same trap as the previous unit, now actually firing — which is why it is drilled twice.
“Partitions whose sums differ by exactly D.” A constraint stated as a difference is almost always a subset-sum target after two lines of algebra.
Call the two sides S1 and S2. They satisfy S1 + S2 = total and S1 − S2 = D, so S2 = (total − D)/2. Counting the subsets that sum to that value counts the partitions. No new recurrence — but the derived target must be checked, because algebra happily produces negative and fractional answers that a table index cannot.
int countPartitions(vector<int>& a, int D) { int total = accumulate(a.begin(), a.end(), 0); if (total - D < 0) return 0; // no such split exists if ((total - D) % 2) return 0; // target would not be an integer return countSubsets(a, (total - D) / 2); }
def countPartitions(a, D): total = sum(a) if total - D < 0 or (total - D) % 2: # no split / not an integer return 0 return countSubsets(a, (total - D) // 2)
Deriving the target and using it unguarded. A negative value indexes the table out of range; an odd one silently truncates to the wrong target and returns a confident count for a question nobody asked.
The problem every other row in this deck is a disguise of
A THIEF WITH A BAG OF CAPACITY W. WHICH ITEMS MAXIMISE THE VALUE CARRIED?
The lecture spends real time proving one approach does NOT work. Which?
Greedy by value fails because a heavy expensive item can block two lighter ones worth more together; greedy by value-per-weight fails too once items cannot be split. He builds an n = 3 counterexample rather than asserting it, and that habit — disprove the cheap idea before writing the expensive one — is worth as much as the recurrence.
What are the two indices of the knapsack table?
Index says which items are still on the table; capacity says how much room is left. Value is what you are MAXIMISING, never part of the state — putting it in the state is the classic beginner error and it makes the table unbounded.
Why is this lecture in a deck whose sheet section never mentions knapsack?
Subset sum is knapsack with value = weight and a boolean answer. Coin change is unbounded knapsack. Rod cutting is unbounded knapsack with length as weight. Learning it once and recognising it five times is far cheaper than learning five problems.
Weights [1, 3, 4, 5], values [1, 4, 5, 7], capacity 7. Greedy by value takes the 7 and is beaten. The table takes the max of skip and take, and TAKE reads the row above, which is precisely what makes each item usable once.
Where the greedy instinct is right, and where the same instinct is wrong
WHEN CAN YOU JUST TAKE THE BIGGEST THING AVAILABLE, AND WHEN DOES THAT LOSE?
Coins {9, 6, 5, 1}, target 11 — the lecture's own counterexample. How many coins does GREEDY use, and how many is optimal?
Greedy grabs 9, is left owing 2, and can only pay it with two 1s — three coins. Taking NO large coin at all gives 6 + 5 = 11 in two. This is the whole reason coin change is a DP problem, and these are the exact denominations from the lecture.
Coins may be reused without limit. What does the TAKE branch do to the index?
He calls this the thumb rule and repeats it: with infinite supply you do not move back after taking, because the same coin is still available. One character of difference from 0/1 knapsack, and it is the only difference.
A target that no combination of coins can reach must return what from the base case?
This is a MIN, so an impossible state must be unattractive — the same identity argument as deck I's out-of-grid cells. Return 0 and impossibility becomes the cheapest option and wins. Most implementations use a large sentinel and convert it to −1 only at the very end.
Striver's own counterexample: coins {9, 6, 5, 1}, target 11. Greedy grabs the 9, owes 2, and pays it with two 1s. three coins. The table finds 6 + 5. Step to the last cell and watch the two disagree; the cells where they differ are tinted.
“Assign each cookie to at most one child.” Note what is NOT here: no target, no subset, no counting. This row is not dynamic programming — it is greedy, and it is in this deck as the control case.
Sort both lists. Offer the smallest cookie to the least greedy child: if it fits, that is a child satisfied with the cheapest possible cookie, and no better use of that cookie exists. If it does not fit, no child can use it, so discard it. Every step is provably safe — which is precisely what the next problem's greedy step is not.
int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(), g.end()); // greediest child last sort(s.begin(), s.end()); // biggest cookie last int child = 0, cookie = 0; while (child < (int)g.size() && cookie < (int)s.size()) { if (s[cookie] >= g[child]) child++; // this cookie satisfies them cookie++; // either way, cookie is spent } return child; }
def findContentChildren(g, s): g.sort(); s.sort() # greediest child, biggest cookie last child = cookie = 0 while child < len(g) and cookie < len(s): if s[cookie] >= g[child]: child += 1 # this cookie satisfies them cookie += 1 # either way, the cookie is spent return child
Concluding from this problem that greedy is generally safe on 'take the best fit' questions. It is safe HERE because the exchange argument holds — swapping in a larger cookie never helps. One slide on, with coins {9, 6, 5, 1}, the same reasoning produces a wrong answer.
“Fewest coins to make an amount”, with unlimited coins of each denomination. Minimisation plus infinite supply — and the obvious greedy answer is wrong.
Greedy takes the biggest coin that fits, and on {9, 6, 5, 1} with target 11 it grabs the 9, owes 2, and pays with two 1s — three coins. Taking no large coin at all gives 6 + 5. So every coin has to be tried at every target, which is the DP. Because supply is unlimited, taking a coin does NOT move past it.
int coinChange(vector<int>& coins, int T) { const int BIG = 1e9; // BIG, never 0: this is a MIN vector<int> dp(T + 1, BIG); dp[0] = 0; for (int t = 1; t <= T; t++) for (int c : coins) // EVERY coin, not the biggest if (c <= t && dp[t - c] + 1 < dp[t]) dp[t] = dp[t - c] + 1; return dp[T] >= BIG ? -1 : dp[T]; }
def coinChange(coins, T): BIG = float('inf') # BIG, never 0: this is a MIN dp = [0] + [BIG] * T for t in range(1, T + 1): for c in coins: # EVERY coin, not the biggest if c <= t: dp[t] = min(dp[t], dp[t - c] + 1) return -1 if dp[T] == BIG else dp[T]
Initialising unreachable targets to 0 rather than a large value. The min then prefers the impossible option at every step and reports a confident, small, wrong number. Same identity argument as deck I's out-of-grid cells.
Signs are a partition wearing different notation
ASSIGN A + OR A − TO EVERY ELEMENT. HOW MANY ASSIGNMENTS REACH THE TARGET?
Assigning + or − to every element, counting the ways to hit a target. What is this the same as?
The plus-signed elements form one subset and the minus-signed ones the other, so their sums differ by exactly the target. It is #05 with the statement rewritten, which is why the lecture is nine minutes long and writes no new recurrence.
Every element must get a sign — none may be left out. Does that break the reduction?
A partition already assigns every element to exactly one side, so 'must be signed' and 'must be partitioned' are the same requirement. Seeing that the constraint is already satisfied — rather than adding machinery for it — is the reduction working.
Array [1, 2, 3, 1], target 3, as in the lecture. How many sign assignments work?
Two: −1+2+3−1 and +1−2+3+1. Total is 7 and the target is 3, so the negative side must sum to (7−3)/2 = 2 — reachable as {2} or as {1,1}, which is exactly two subsets. The reduction gives the count without enumerating signs at all.
“Assign + or − to every element to reach a target.” Two groups, every element in exactly one, a constraint on the difference of their sums. That is a partition with a given difference, written in other notation.
The plus-signed elements form one subset and the minus-signed ones the other. Their sums differ by exactly the target, so counting valid sign assignments is counting partitions with difference = target — problem #05, unchanged. The 'every element must be signed' requirement is not an extra constraint: a partition already puts every element on one side.
int findTargetSumWays(vector<int>& a, int target) { // + signed elements and - signed elements are two subsets whose sums // differ by `target`. That is problem #05, verbatim. int total = accumulate(a.begin(), a.end(), 0); if (total - abs(target) < 0) return 0; if ((total - abs(target)) % 2) return 0; return countSubsets(a, (total - abs(target)) / 2); }
def findTargetSumWays(a, target): # + signed and - signed elements are two subsets whose sums differ by # `target`. That is problem #05, verbatim. total = sum(a) d = total - abs(target) if d < 0 or d % 2: return 0 return countSubsets(a, d // 2)
Writing a fresh recurrence over signs. It works, it is slower to derive, and it duplicates code you already have. The expensive mistake here is not a bug — it is failing to notice that the problem is already solved.
Counting with unlimited supply, and why order never double-counts
HOW MANY COMBINATIONS OF COINS ADD UP TO THE AMOUNT, REUSE ALLOWED?
Coin Change 2 counts combinations rather than minimising coins. Which two things change from #07?
Same table, same infinite-supply take branch, min swapped for a sum — and the base case flips from a large sentinel to a 1, because paying the target exactly IS one valid combination. Deck I's stairs-versus-frog contrast, one dimension up.
Why does this count COMBINATIONS rather than permutations — why is 1+2 not counted separately from 2+1?
Not-pick moves permanently past a coin, so every combination is generated in exactly one index order. Swap the loop order in the tabulated version and you start counting permutations instead — the classic coin-change trap, and it is a difference in the ITERATION, not in the recurrence.
The take branch is guarded before it runs. What does the guard check?
Taking a coin larger than what you still owe would drive the target negative and index the table out of range. He states it as a condition on the take branch rather than as a base case — cheaper, and it keeps the base case about the array rather than about the target.
“How many combinations of coins make the amount”, unlimited supply. Counting plus infinite supply — problem #07's table with the operator swapped.
Same states, same infinite-supply take branch, but min becomes a sum and the base case becomes 1: paying the amount exactly IS one combination. The subtlety is ordering — because not-pick moves permanently past a coin, each combination is generated in exactly one coin order, so 1+2 and 2+1 are never counted twice.
int change(int amount, vector<int>& coins) { vector<long long> dp(amount + 1, 0); dp[0] = 1; // paying exactly IS one combination for (int c : coins) // coins OUTSIDE: combinations for (int t = c; t <= amount; t++) // targets INSIDE, forward dp[t] += dp[t - c]; // take stays on the same coin return (int)dp[amount]; }
def change(amount, coins): dp = [0] * (amount + 1) dp[0] = 1 # paying exactly IS one combination for c in coins: # coins OUTSIDE: combinations for t in range(c, amount + 1): # targets INSIDE, forward dp[t] += dp[t - c] # take stays on the same coin return dp[amount]
Swapping the loops. Targets outside and coins inside counts PERMUTATIONS — 1+2 and 2+1 become two answers — and the number returned is larger and entirely believable. The recurrence on paper is unchanged, which is what makes it hard to spot.
0/1 knapsack with one index changed
THE SAME BAG, BUT NOW EVERY ITEM HAS UNLIMITED COPIES. WHAT CHANGES?
The lecture names its prerequisite in the first minute. What is it?
He says to go and watch 0/1 knapsack before this one, because unbounded knapsack is defined as the difference from it. That is also why this deck keeps DP 19 despite the sheet having no row for it — the lecture after it does not stand alone.
State the entire difference between 0/1 and unbounded knapsack.
That is genuinely all of it. Same table, same capacity index, same max — one branch does not decrement the index. Being able to state a difference this precisely is what makes the family collapse into one thing you actually remember.
0/1 knapsack over n items space-optimises to a single row. Does unbounded?
Because the take branch stays at the same index, the row you are writing is the row you want to read — so a single array iterated in increasing capacity is correct, and it is the 0/1 version that has to be careful about direction. The one place unbounded is the easier of the two.
Weights [2, 4, 6], values [5, 11, 13], capacity 10. The entire difference from 0/1: the TAKE branch reads its own row instead of the one above, so the item it just used is still available. Watch the source cell stay level rather than rising.
A knapsack statement with the words “infinite supply” or “any number of times” in it. Everything else about the problem is 0/1 knapsack.
In 0/1 knapsack the take branch moves to the previous item, which is what makes each item single-use. Remove that one decrement and the item stays available. That is the complete difference — and it is also why the space-optimised version iterates capacity FORWARD, so the cell it reads has already been updated for this item.
int unboundedKnapsack(vector<int>& w, vector<int>& v, int W) { vector<int> dp(W + 1, 0); for (int i = 0; i < (int)w.size(); i++) for (int c = w[i]; c <= W; c++) // FORWARD: dp[c-w[i]] is this row, dp[c] = max(dp[c], // already updated, so the item v[i] + dp[c - w[i]]); // can be taken again return dp[W]; }
def unboundedKnapsack(w, v, W): dp = [0] * (W + 1) for i in range(len(w)): for c in range(w[i], W + 1): # FORWARD: dp[c-w[i]] is this row, dp[c] = max(dp[c], # already updated, so the item v[i] + dp[c - w[i]]) # can be taken again return dp[W]
Reading dp[i-1][c-w[i]] out of habit. Each item then gets used at most once, the total comes out lower, and nothing about the code looks wrong — it is the 0/1 solution answering an unbounded question.
Reframing a statement until a solved problem appears underneath it
CUT A ROD OF LENGTH n INTO PIECES TO MAXIMISE WHAT THE PIECES SELL FOR.
The lecture reframes the statement before solving it. From what, to what?
Cutting is hard to write a recurrence for; COLLECTING is unbounded knapsack, which is already solved. Turning a problem around until it becomes one you have done is the single most transferable move in this deck.
Mapped onto unbounded knapsack, what plays the part of the WEIGHT?
Length is what the rod's total capacity is spent on, so length is weight and the rod's length is the capacity; price is the value being maximised. Getting this mapping right is the entire problem — after it, the code is the previous lecture's.
Why can a rod length be used more than once, making this unbounded rather than 0/1?
A rod of length 8 can perfectly well be cut into four pieces of length 2. There is no constraint saying each length is available once, so the take branch stays put — the same test you apply to every problem in this group.
“Cut a rod into pieces to maximise the total price.” Cutting is hard to recurse on directly — but the pieces have to sum to the rod's length, and that is a capacity.
Turn it around: instead of breaking a rod of length n, COLLECT piece lengths that sum to n, maximising their total price. Now length is weight, the rod's length is the capacity, and price is value — unbounded knapsack, because nothing stops you cutting two pieces the same length. There is no new code to write once the statement has been reframed.
int cutRod(vector<int>& price, int n) { // length is the WEIGHT, the rod is the CAPACITY, price is the VALUE. // A length may be cut more than once, so this is UNBOUNDED knapsack. vector<int> dp(n + 1, 0); for (int len = 1; len <= n; len++) for (int c = len; c <= n; c++) dp[c] = max(dp[c], price[len - 1] + dp[c - len]); return dp[n]; }
def cutRod(price, n): # length is the WEIGHT, the rod is the CAPACITY, price is the VALUE. # A length may be cut more than once, so this is UNBOUNDED knapsack. dp = [0] * (n + 1) for length in range(1, n + 1): for c in range(length, n + 1): dp[c] = max(dp[c], price[length - 1] + dp[c - length]) return dp[n]
Trying to recurse on the CUTS — 'cut here, then solve both halves'. It is correct and it is a partition DP, which is deck IV's material and far more work. The whole lesson of this lecture is that reframing the statement removes the difficulty instead of managing it.
Same table, same two source cells. Which operator answers 'how many ways'?
Add. Pick and not-pick are disjoint — no subset both takes and skips an element — so their counts sum. OR answers reachability, MIN or MAX answers optimisation, and the recursion underneath never changed.
Which single change turns 0/1 knapsack into unbounded knapsack?
One index. dp[i-1][c-w[i]] becomes dp[i][c-w[i]], so the item you just used is still on the table. Being able to state the difference in one clause is what collapses coin change, unbounded knapsack and rod cutting into a single thing worth remembering.
Counting partitions whose sums differ by D. Which target do you count subsets for?
(total − D) / 2. The smaller side is S2, and S1 + S2 = total with S1 − S2 = D. Guard it twice before using it — negative means no such split exists, odd means it is not an integer — and Target Sum is this same reduction with the statement rewritten in plus and minus signs.
A minimum-coins DP hits a target no combination can reach. The base case returns…
The identity for a min is +∞. Return 0 and impossibility becomes free and wins every comparison. Exactly the argument deck I made about out-of-grid cells — the value comes from the OPERATOR, and it does not care that this is coins rather than a grid.
Coin Change 2 counts combinations. What stops 1 + 2 and 2 + 1 counting as two?
Each combination is generated in exactly one index order. Once not-pick has moved past a coin it never comes back, so an ordering is never revisited. Swap the two loops in the tabulated version and you start counting permutations — a difference in the ITERATION, not in the recurrence.
Rod cutting is unbounded knapsack. What plays the part of the weight?
Length is weight, the rod is the capacity, price is the value. The lecture turns 'break n into pieces' into 'collect lengths summing to n, maximising price' — and once it is phrased that way there is no new code to write. Reframing until a solved problem appears is the move worth stealing.
Four of these six return a NUMBER rather than an error, and three of them return the right number on the inputs you are most likely to try. A zero in the array, a swapped pair of loops, an index that should not have moved.
vector<vector<bool>> dp cannot say 'not computed yet', so every state either recomputes or returns a stale false. Use int and −1. The answer stays right and the runtime stays exponential, which is the worst combination.
A zero can be taken or skipped, so each one DOUBLES the number of subsets. The base case owes 2, not 1. Invisible on arrays of positive integers, which is exactly where it hides until a later problem loosens the constraints.
Minimum coins for an unreachable target must return a large value. Return 0 and the impossible option is free, wins every min, and the function reports a small number with total confidence.
(total − D) / 2 must be non-negative AND even. Skip either check and you index the table with a negative number or silently truncate a half — a wrong count rather than a crash.
dp[i-1][c-w[i]] in an unbounded problem lets each item be used once. The answer is still plausible, merely too small, and nothing about the code looks wrong.
Iterating targets outside and coins inside counts PERMUTATIONS: 1+2 and 2+1 become two answers. The number returned is larger and entirely believable, and the recurrence on paper is unchanged.
Eleven rows, one table. The right column is the transition — read down it and notice how little actually changes between them.
Every problem here was the same two branches over the same table: take this element and reduce what you owe, or skip it and don't. OR them for reachability, ADD them to count, MIN or MAX them to optimise, and stop decrementing the index when supply is unlimited. The rest was algebra — equal halves, a given difference and a page of plus and minus signs all collapsed onto one subset-sum target. Deck III moves the second index onto a SECOND STRING, which is where the same table starts comparing two sequences instead of paying off a number.
Deck 2 of 4. Lectures DP 14-24 of 56. Eleven of the sheet's 55 rows. DP 19 (0/1 Knapsack) is a lecture with no sheet row and runs as a concept unit; Assign Cookies is a sheet row with no lecture and is not a DP problem — it sits beside Minimum Coins so the pair can be compared. Every drill cites its lecture transcript; every bench fills in numbers the build re-derived and asserted against brute force.
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.