To make an amount with the fewest coins, think about the last coin: whichever it is, the rest must be made as cheaply as possible. So fill dp[a] for every amount from 0 up, each from dp[a − c] + 1 for every coin c, and read the coins back from the record of winning last coins.
- Average time
- O(nA)
- Space
- O(A)