Why it works
- Whatever coins pay a, one of them is paid last. If it is c, the rest pays a − c, and in the best case with dp[a − c] coins. So dp[a] is the smallest dp[a − c] + 1 over all coins.
- ∞ keeps the amounts that cannot be paid out of the minimum: ∞ + 1 is still ∞. That is why the coin 6 gives nothing at 10 — the 4 left over is ∞ — and the largest coin is not always the right one.
- The amounts go up from 1, and a − c is always smaller than a, so every cell a cell reads is already final.
Complexity
Time O(amount × coins): every amount tries every coin once. Memory O(amount): one cell per amount from 0 up.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗