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 a denomination of 5, we get a similar problem with 95 as the target amount.
The code for recursive solution is like this:
Optimization with memorization
In the backtracking solution, there is a lot of repeated computation. We can see from the 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 a HashMap(or an array) to save the results of sub-problem and reducing unnecessary recursion.
Dynamic programming: bottom-up
The 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 minimum 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 kinds of coins.