Where it runs
1. The problem
Back in lesson 105 you paid out change the greedy way: take the biggest coin that fits into what is left, and repeat. For normal money that always gives the fewest coins. The same lesson showed that the rule works only on a "canonical" coin set (a set where the greedy choice is always the best).
Here is a set where it breaks. Coins [1, 3, 4], and you owe 6. Greedy takes the 4, then two 1s: 4 + 1 + 1, three coins. Yet 3 + 3 is only two coins. Taking the big coin first left 2, and 2 can only be paid with two 1s.
For such sets the greedy shortcut won't do. You need a method that tries every coin at every amount and remembers the best. A table does that. It returns the fewest coins that add up to the amount, or -1 if the amount can't be made exactly. You can use each coin as many times as you like.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- best/maximum/minimum ending at position i
- ways to reach, climb, or tile
- cannot pick two adjacent items
- minimum cost path through a grid
- overlapping subproblems, same state recomputed
Looks similar, isn't
- Recursion with memoization
Memoisation fills the same table from the top, on demand. This fills it upward in a fixed order.
- Greedy (exchange argument)
Greedy commits to one choice per step. DP keeps every option until the end.
- Recursion
The recursion tells you what the transition is. The table is what makes it fast.
- DP on subsequences (LIS / LCS / edit distance)
There the state is a pair of positions in two sequences. Here one index is enough.
n states with O(1) work each gives O(n). Memory drops to O(1) when only the last states matter.
On LeetCode
Problems that build an amount from pieces you can reuse, asking for the fewest pieces or the number of ways. A table indexed by amount, filled from 0 up, tries every piece at every amount.
The lesson task. Zero coins make the amount 0, and an amount still at infinity at the end gives minus 1.
Here the table counts ways. Put the coin loop outside the amount loop so each mix of coins is counted once, whatever its order.
The coins are the square numbers up to n, and the table gives the fewest of them that add up to n.
Here different orders count as different answers, so the amount loop goes outside and the number loop inside.