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
.
Example 1:
coins = [1, 2, 5]
, amount = 11
return 3
(11 = 5 + 5 + 1)
Example 2:
coins = [2]
, amount = 3
return -1
.
Note:
You may assume that you have an infinite number of each kind of coin.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
This article is for intermediate users. It introduces the following ideas: Backtracking, Dynamic programming.
Intuition
The problem could be modeled as the following optimization problem :
, where is the amount, is the coin denominations, is the number of coins with denominations used in change of amount . We could easily see that .
A trivial solution is to enumerate all subsets of coin frequencies that satisfy the constraints above, compute their sums and return the minimum among them.
Algorithm
To apply this idea, the algorithm uses backtracking technique to generate all combinations of coin frequencies in the range which satisfy the constraints above. It makes a sum of the combinations and returns their minimum or in case there is no acceptable combination.
Java
public class Solution { public int coinChange(int[] coins, int amount) { return coinChange(0, coins, amount); } private int coinChange(int idxCoin, int[] coins, int amount) { if (amount == 0) return 0; if (idxCoin < coins.length && amount > 0) { int maxVal = amount/coins[idxCoin]; int minCost = Integer.MAX_VALUE; for (int x = 0; x <= maxVal; x++) { if (amount >= x * coins[idxCoin]) { int res = coinChange(idxCoin + 1, coins, amount - x * coins[idxCoin]); if (res != -1) minCost = Math.min(minCost, res + x); } } return (minCost == Integer.MAX_VALUE)? -1: minCost; } return -1; } } // Time Limit Exceeded
Complexity Analysis
Intuition
Could we improve the exponential solution above? Definitely! The problem could be solved with polynomial time using Dynamic programming technique. First, let's define:
- minimum number of coins needed to make change for amount using coin denominations
We note that this problem has an optimal substructure property, which is the key piece in solving any Dynamic Programming problems. In other words, the optimal solution can be constructed from optimal solutions of its subproblems. How to split the problem into subproblems? Let's assume that we know where some change for which is optimal and the last coin's denomination is . Then the following equation should be true because of optimal substructure of the problem:
But we don't know which is the denomination of the last coin . We compute for each possible denomination and choose the minimum among them. The following recurrence relation holds:
In the recursion tree above, we could see that a lot of subproblems were calculated multiple times. For example the problem was calculated times. Therefore we should cache the solutions to the subproblems in a table and access them in constant time when necessary
Algorithm
The idea of the algorithm is to build the solution of the problem from top to bottom. It applies the idea described above. It use backtracking and cut the partial solutions in the recursive tree, which doesn't lead to a viable solution. Đ¢his happens when we try to make a change of a coin with a value greater than the amount . To improve time complexity we should store the solutions of the already calculated subproblems in a table.
Java
public class Solution { public int coinChange(int[] coins, int amount) { if (amount < 1) return 0; return coinChange(coins, amount, new int[amount]); } private int coinChange(int[] coins, int rem, int[] count) { if (rem < 0) return -1; if (rem == 0) return 0; if (count[rem - 1] != 0) return count[rem - 1]; int min = Integer.MAX_VALUE; for (int coin : coins) { int res = coinChange(coins, rem - coin, count); if (res >= 0 && res < min) min = 1 + res; } count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min; return count[rem - 1]; } }
Complexity Analysis
Time complexity : . where S is the amount, n is denomination count. In the worst case the recursive tree of the algorithm has height of and the algorithm solves only subproblems because it caches precalculated solutions in a table. Each subproblem is computed with iterations, one by coin denomination. Therefore there is time complexity.
Space complexity : , where is the amount to change We use extra space for the memoization table.
Algorithm
For the iterative solution, we think in bottom-up manner. Before calculating , we have to compute all minimum counts for amounts up to . On each iteration of the algorithm is computed as
In the example above you can see that:
Java
public class Solution { public int coinChange(int[] coins, int amount) { int max = amount + 1; int[] dp = new int[amount + 1]; Arrays.fill(dp, max); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int j = 0; j < coins.length; j++) { if (coins[j] <= i) { dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; } }
Complexity Analysis
Analysis written by: @elmirap.