DP I: linear and knapsack

What is the difference between memoization and tabulation?

They compute the same values in a different order. Memoization is the recursion you already wrote plus a cache, so it starts at the answer and works down, and it only ever computes the subproblems it actually needs. Tabulation is a loop that fills the same cells from the base case upwards. Tabulation avoids Python’s recursion limit and lets you drop the table to a couple of variables when each cell reads only its neighbours. In an interview either is fine, and memoization is usually faster to write.

How do I work out what the DP state should be?

Ask what the last decision is, then ask what you would need to know to make it. For House Robber the last decision is whether to rob the last house, and the only thing you need to know is where the street you are still choosing from ends, so one index is enough. For knapsack you also need to know how much room is left, so the state gains a second number. Write the meaning of one cell as a single exact sentence before you write any code; if you cannot, you do not have the state yet.

Why does 0/1 knapsack iterate the capacity backwards?

In the one-row version, dp[c] reads dp[c - w], a cell to its left. Going downwards, that left-hand cell has not been touched yet during this item’s pass, so it still holds the value from before the item existed, and the item can go in at most once. Going upwards, the left-hand cell has already been updated with this item, so the item goes in again and again. That is the unbounded problem, which is what Coin Change wants, and it is why Coin Change loops upwards on purpose.

Why is knapsack called pseudo-polynomial if it runs in O(n × capacity)?

Because the capacity is a value in the input, not a measure of how long the input is. A capacity written as a 40-digit number takes 40 characters to write down and produces a table with 10 to the 40th columns. The running time is polynomial in the numbers, not in the size of the input, and that is what pseudo-polynomial means. It matters in an interview only if the constraints allow a huge capacity, which is why you read the constraints before choosing this shape.

When is a greedy choice enough, and when do I need DP?

Greedy is enough when taking the locally best option provably never rules out the best overall answer, and you have to be able to make that argument. Coin change with 1, 5, 10 and 25 is greedy-safe because every coin is a multiple of the smaller ones. Coin change with 1, 3 and 4 is not: greedy pays 6 with 4 + 1 + 1, and the answer is 3 + 3. When you cannot prove the exchange argument, try every choice at the last step and cache the results, which is DP.