Two-dimensional Dynamic Programming
Counting, where the loop order changes the answer
The subtlest thing in either DP unit. Two nested loops, swapped, count two different things.
Key idea
Two questions that sound the same
How many ways can these pieces make the target? That sentence is ambiguous, and the ambiguity is the whole lesson.
If a 1 then a 2 is the same as a 2 then a 1, you are counting combinations. If they are different, you are counting arrangements. Most problems want combinations, and the natural loop counts arrangements.
The two versions differ only in which loop is outer. Nothing else changes, and the answers are not close.
Here is the natural loop, which counts arrangements, with the same question listed out by hand underneath so the gap is visible.
Why it works
Why the outer loop decides it
With amounts outside, every size is tried at every amount, so a total is built in every possible order and each order is counted once. That is arrangements: 1+1+2, 1+2+1, and 2+1+1 are three.
With pieces outside, the table is completed for one piece before the next is considered. So by the time a size is being used, every way already counted uses only sizes at or before it in the list. That imposes a fixed order on the pieces and each combination is therefore reached exactly once.
Say that second sentence out loud until it is convincing. It is the reason, and it is the part that people memorize instead of understanding.
Tip
Check with a tiny case
Target 4 with pieces 1 and 2. The combinations are 1+1+1+1, 1+1+2, and 2+2, which is three. The arrangements are those plus the reorderings of 1+1+2, which is five.
That case is small enough to enumerate by hand in ten seconds and it distinguishes the two versions immediately. Whenever you write one of these, run it against a case you have counted manually.
Key idea
This is a two-dimensional table collapsed
The combinations version is really a table indexed by which pieces are allowed and by the amount. The row for the first k pieces is built from the row for the first k minus 1.
Collapsing it to one array works because each row only reads the row above and cells to its left, which is why the pieces loop must be outermost. Seeing the collapsed version as a two-dimensional table is what makes the loop order obvious rather than arbitrary.
Below, nothing is computed. Each cell of one row is asked only where it reads from.
Why it works
Which row the reuse term reads
The reuse term reads the same row at a smaller amount, which is what allows a piece to be used repeatedly. Reading the row above instead would allow it only once, and that is exactly the subset-sum distinction from U14.
So the two knapsack variants differ by one index in one term. Being able to point at that index and say which problem it makes is worth more than remembering either formula.
Cost
Cost
O(pieces times target) time either way, and O(target) space for the collapsed version or O(pieces times target) for the explicit table.
As in U14, the target is a value rather than an input length, so this is pseudo-polynomial.
Which loop belongs on the outside?
Both versions have the same two loops, the same table, and the same update. Only the nesting differs. Which nesting counts each multiset once, so that 1 then 2 and 2 then 1 are not counted separately?
Coin Change Ii
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.