Question bank — DP problems — Fibonacci, coin change (count + min), 0 - 1 knapsack

False. Fibonacci and coin change are 1D; the table's shape equals the number of things the future actually depends on (its "state"). Only when two independent quantities matter (item index and remaining capacity) do you need 2D.

False. Memoization (top-down) only computes subproblems the recursion actually reaches; tabulation (bottom-up) fills the whole table, including cells that may never be needed. See Tabulation vs Memoization.

False. Optimal substructure alone (with no repeated subproblems) is just plain divide-and-conquer — merge sort has optimal substructure but zero overlap, so caching buys nothing.

False. dp[0] = 1 means there is exactly one way to make amount 0 — the empty selection (use nothing). It is a count of ways, not a count of coins.

False. Different meaning: min counts coins, and making 0 needs zero coins, so dp[0] = 0. Count measures ways (one way: empty), min measures coins (zero coins). Same cell, different quantity.

False. Only for "canonical" systems like 1,5,10,25. For coins = [1,3,4], target 6, greedy gives 4+1+1 = 3 coins but DP finds 3+3 = 2. Greedy has no optimal substructure guarantee for arbitrary denominations.

True. In 1D form, iterating weight downward means dp[w-wi] still holds the previous item (used at most once → 0/1); iterating upward means dp[w-wi] may already include item i (reused → unbounded). One direction flip is the entire difference.

False. It is slow because the recursion tree has ≈ φⁿ nodes — the same F(k) is recomputed exponentially many times. Memory kills the repeats, not faster arithmetic. See Time and Space Complexity.

False. It stays Θ(n) time; only space drops from Θ(n) to Θ(1). Space and time are independent axes — trimming the table doesn't reduce the number of additions.

False. Coins outside counts combinations; putting amount outside counts permutations, so 1+2 and 2+1 get counted separately and the total inflates.

Wrong. Forward iteration lets dp[w-wi] already contain item i, so item i is reused → you've silently written unbounded knapsack. Fix: loop w from W down to wi.

Missing the +1. Each choice of "last coin c" spends one coin, so it is dp[a-c] + 1. Without the +1 every dp collapses toward dp[0] and reports far too few coins.

Wrong row. It must be dp[i-1][w-wi]. Referencing row i would allow item i to be taken again — that's reuse, which 0/1 forbids. The i-1 is what enforces "at most once."

Wrong. They must start at ∞ (a sentinel meaning "impossible"). Starting at 0 makes the min() happily build impossible amounts out of nothing and return a bogus small count.

Dangerous. A mutable default is shared across all calls, so the cache leaks between separate top-level invocations. It happens to speed things up here, but it's a well-known trap; pass memo explicitly or use None. See Recursion and Memoization.

Wrong. Skipping item i means capacity is untouched, so weight stays w. Only the take branch subtracts wi. Mixing them corrupts the meaning of the state.

Because dp[a] += dp[a-c] needs a nonzero seed: a coin of exact value a should count as one valid way, and that way is "make a-c=0 with nothing, then add c." dp[0]=1 injects that single empty way so it can propagate.

It fixes a coin order. Once coin c's loop is done, later coins can only be added after c, so a combination is built in one canonical order — 1+2 exists but 2+1 never gets a second path.

Fibonacci's future depends only on which index you're at. Knapsack's future depends on two things — which items remain and how much room is left — so a single index can't describe the state.

Min measures a cost, so using one more coin adds 1 to the total (+1). Count measures how many ways exist, so choosing a coin doesn't add cost — it pools all the ways of the sub-target into the current count (+=).

Going high→low, when you update dp[w] you read dp[w-wi], which is a lower index not yet touched this round — so it still holds row i-1's value. Going low→high, dp[w-wi] was already overwritten with item i.

With 1,5,10,25 each larger coin is a "clean" multiple-ish jump so grabbing the biggest never traps you. With [1,3,4], grabbing 4 for target 6 strands you at 2 (needing two 1s), whereas two 3s were cheaper — greedy has no proof of optimality here.

F(i) depends only on the two rows below it, so a rolling window of 2 suffices. Knapsack's dp[i][w] depends on the entire previous row across all capacities, so you keep a full row (which is why 1D knapsack keeps one array, not two scalars).

Answer is 1, not 0 — the empty selection makes 0. This is exactly why dp[0] is initialized to 1; the "trivial" case is a real combination.

dp[amount] stays ∞, and the function returns -1. The ∞ sentinel is what lets you detect impossibility instead of returning a wrong finite number.

The answer is 0 value — no item fits, and the whole dp row is 0. The base row/column of zeros already encodes this; no special case needed.

The "take" branch is never enabled (its guard wi ≤ w always fails), so dp collapses to all-skip and returns 0. Nothing breaks — the guard handles it automatically.

F(0)=0 and F(1)=1 are the base cases; the loop/recurrence only starts at n ≥ 2. Forgetting either base makes the whole sequence shift or crash on the first recursive call.

Count is 1 only for amount 0 (empty set) and 0 for any positive amount; min returns -1 for any positive amount. The base cases still hold — the loops over coins simply never execute.

Yes — set each item's value equal to its weight (or use a boolean reachability table); it's the same "take/skip, at most once" structure. See Subset Sum and Partition Problems.

Yes, when no item's weight is small enough to fit twice within W — reuse becomes impossible, so up-loop and down-loop give identical answers. See Unbounded Knapsack and Rod Cutting.