Unbounded knapsack, minimising count. The direction of the capacity loop is the whole distinction:

• Ascending capacity: dp[a - c]dp[a - c] may already include coin cc, so coins are reusable — unbounded.
• Descending capacity: dp[a - c]dp[a - c] is from the previous item’s row, so each coin is used at most once — 0/1.

Time $O(\text{amount} \times \text{len(coins)})$. Space $O(\text{amount})$.

• amount = 0amount = 0 returns 0, and dp = [0]dp = [0] handles it with no loop iterations.
• Greedy largest-first fails. coins = [1,3,4], amount = 6coins = [1,3,4], amount = 6 greedily takes 4+1+1 = 3 coins; the answer is 3+3 = 2. Greedy is only correct for canonical systems, and real currency happens to be one — which is why the intuition is so sticky and so wrong here.
• Unreachable amounts must return -1-1, not infinity. [2][2] with amount = 3amount = 3 is the check.
• Huge denominations are harmless: the c <= ac <= a guard skips any coin bigger than the current amount, so 2**31 - 12**31 - 1 never indexes out of range.

Follow-ups you should expect: “Which coins?” — store the coin that improved each dp[a]dp[a] and walk back from amountamount. “Count the combinations instead (LC 518)?” — loop coins outside and amounts inside, and sum; the loop order is what stops permutations being double-counted. “Count permutations (LC 377)?” — swap those loops. “At most kk of each coin?” — bounded knapsack, solved with binary splitting of the counts. “Amount up to $10^9$?” — the DP dies and it becomes a number-theory problem.

The tell is “at most mm zeros and at most nn ones”: two independent resources, so the capacity is a pair. Everything else is standard 0/1 knapsack with every item’s value equal to 1.

Time $O(\text{len(strs)} \times m \times n)$ — about $600 \times 100 \times 100 = 6 \times 10^6$ here. Space $O(mn)$.

• Both loops must descend. If either ascends, a string can be reused inside its own pass and you overcount. The given examples will not catch the bug — both loop directions answer [4, 2, 2][4, 2, 2]. The smallest input that does is ["0"]["0"] with m = 2, n = 1m = 2, n = 1: the answer is 1, and an ascending loop says 2, having spent the single string twice.
• The item loop stays outermost. Rolling a 2D array in place only works because each string is fully processed before the next begins.
• A string that fits neither budget is skipped automatically: `range(m, zeros
  • 1, -1)is empty whenis empty whenzeros > m`, so no guard is needed.
• mm or nn equal to 0 is outside LeetCode’s constraints, but the code still handles it — the grid is a single row or column and only free items would fit.

Follow-ups you should expect: “Which strings?” — keep the full 3D table dp[k][i][j]dp[k][i][j] and backtrack, or store parents. “Maximise total length instead of count?” — the item value becomes len(s)len(s); nothing else changes. “Three resources?” — a third descending loop, and the constant factor stops being friendly. “Can this be greedy by shortest string first?” — no; a short string may eat the one zero a much better pair needed.

The reduction is the interview. Once you see that every schedule assigns each stone a ++ or a --, the problem reads: split the stones into groups $A$ and $B$ minimising $|{\sum A} - {\sum B}|$. Writing $\sum A = b$ and $\sum B = \text{total} - b$, the difference is $\text{total} - 2b$, minimised by the largest $b \le \lfloor \text{total}/2 \rfloor$ you can actually reach. That is subset sum.

Why the reduction holds, in both directions: any schedule expands into a signed sum by induction on the smashes, and conversely any sign assignment is realisable — smash within each group down to one stone each, then smash those two together. The total - 2btotal - 2b form with b <= total // 2b <= total // 2 also guarantees the result is non-negative, so no absolute value is needed.

Time $O(n \times \text{total})$, at most $30 \times 3000$. Space $O(\text{total})$.

• total // 2total // 2 floors, which is what you want: for an odd total the two groups cannot tie and the best difference is 1.
• [1,1][1,1] gives 0 — the two stones annihilate. [1][1] gives 1 — nothing to smash, so total - 2 * 0total - 2 * 0.
• The r + s <= targetr + s <= target filter is what keeps the set small and is also why max(reachable)max(reachable) is the right pick; without the cap you would need the value nearest to half from below.
• Building a new set inside the comprehension is the set-based equivalent of the descending loop: you must not iterate a set you are mutating, and you must not let stone ss be added twice.

Follow-ups you should expect: “How is this different from LC 1046, Last Stone Weight?” — that one fixes the schedule as always-smash-the-two-largest, so it is a heap problem, not DP. Knowing why the greedy is correct there and wrong here is the point. “Return the two groups?” — track predecessors, or use a boolean table instead of a set. “Bitset trick?” — bits |= bits << sbits |= bits << s, then scan down from targettarget for the highest set bit; Python’s big ints make this very fast. “All stones equal?” — the answer is 0 for an even count, stones[0]stones[0] for an odd one.