You are given coins of different denominations and a total amount of money amount.
Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
This is a classic problem with a backtracking solution. We can recursively try to solve a smaller problem. If we want to know how many coins need for 100, we subtract a coin with denomination of 5, we get a similar problem with 95 as target amount.
The code for recursive solution is like this:
Optimization with memorization
In the backtracking solution, there are a lot of repeated computation. We can see from below diagram, the sub-problem of
7 are all computed more than two times.
An optimization is removing these duplicated computations. The general algorithm design guide for this kind of problem is search memorized optimization, and use an HashMap(or an array) to save the results of sub-problem and reducing unnecessary recursion.
Dynamic programming: bottom-up
Above solution is a strategy of top-bottom. We can also use a bottom-up approach to think about it. We define
F(i) as the minimum number of coins required to form the amount
i, assuming we have already known the value of
F(0), F(1) ... F(i-1), then the value of
F(i) should be the minimal value of
j start from 0 to
The time complexity is: $O(Sn)$, where
S is the target amount, and
n is the number of different kind of coins.