322. Coin Change
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return 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.
Example 1:
Example 2:
Example 3:
Constraints:
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
Solution:
Approach 1 (Brute force) [Time Limit Exceeded]
class Solution {
public int coinChange(int[] coins, int amount) {
int index = 0;
return helper(0, coins, amount);
}
private int helper(int index, int[] coins, int amount){
if (amount == 0){
return 0;
}
if (index == coins.length){
return -1;
}
int branches = amount/coins[index];
int minCost = Integer.MAX_VALUE;
for (int i = 0; i <= branches; i++){
if (amount >= i * coins[index]){
int res = helper(index + 1, coins, amount - i * coins[index]);
if (res != -1){
minCost = Math.min(minCost, res + i);
}
}
}
if (minCost == Integer.MAX_VALUE){
return -1;
}else{
return minCost;
}
}
}
// [1, 2, 5]
/* / \
level 0: 1
0/ |||.. \ 11 /1 = 11
level 1:
*/
// level: index of coins
// branch: means the how many coins I will pick up
// TC: O(branch^level) = O(S^n)
// SC: O(level) = O(n)
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];
}
}
/*
1 2 5
11
/ | \
0level 5 0 1 2
/ \ / \ / \
1level 2 2
level coins value
branch number of coins
*/
Approach 2 (Dynamic programming - Top down) [Accepted]
class Solution {
private Integer[] memo;
public int coinChange(int[] coins, int amount) {
memo = new Integer[amount+1];
return helper(coins, amount);
}
private int helper(int[] coins, int amount){
if (amount < 0){
return -1;
}
if (amount == 0){
return 0;
}
if (memo[amount] != null){
return memo[amount];
}
int minCount = Integer.MAX_VALUE;
// branch
for (int coin : coins){
int count = helper(coins, amount - coin);
if (count == -1){
continue;
}
minCount = Math.min(minCount, count + 1);
}
if (minCount == Integer.MAX_VALUE){
memo[amount] = -1;
}else{
memo[amount] = minCount;
}
return memo[amount];
}
}
// TC: O(branch^level) = O(n^S)
// SC: O(S)
/*
level means: amount
branch means: index[coins]
memo [amount+1]
1, 2, 5
11
/ | \
level
*/
Approach 3 (Dynamic programming - Bottom up) [Accepted]
For the iterative solution, we think in bottom-up manner. Before calculating \(F(i)\), we have to compute all minimum counts for amounts up to \(i\). On each iteration iii of the algorithm \(F(i)\) is computed as \(min_{j=0 \ldots n-1}{F(i -c_j)} + 1\)
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// dp[i] stroes the fewest the number of coins to make up amount i
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++){
for (int coin : coins){
if (i - coin < 0){
continue;
}
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
if (dp[amount] == (amount + 1)){
return -1;
}else{
return dp[amount];
}
}
}
// 1,2 5
// TC: O(S*N)
// SC: O(S)
// i: 0 1 2 3 4 5 6 7 8 9 10 11
// dp[i] 0 1 1 2 2 1 2 2 3 3 2 3
class Solution {
private Integer[] memo;
public int coinChange(int[] coins, int amount) {
memo = new Integer[amount + 1];
int index = 0;
// return helper(index, coins, amount);
return helper(coins, amount);
}
private int helper(int[] coins, int amount){
if (amount < 0){
return -1;
}
if (amount == 0){
return 0;
}
// if (index == coins.length){
// return -1;
// }
if (memo[amount] != null){
return memo[amount];
}
// int branches = amount/coins[index];
int minCost = Integer.MAX_VALUE;
// for (int i = 0; i <= branches; i++){
// if (amount >= i * coins[index]){
// int res = helper(index + 1, coins, amount - i * coins[index]);
// if (res != -1){
// minCost = Math.min(minCost, res + i);
// }
// }
// }
for (int coin : coins){
int res = helper(coins, amount - coin);
if (res == -1){
continue;
}
minCost = Math.min(minCost, res + 1);
}
// if (minCost == Integer.MAX_VALUE){
// return -1;
// }else{
// return minCost;
// }
if (minCost == Integer.MAX_VALUE){
memo[amount] = -1;
}else{
memo[amount] = minCost;
}
return memo[amount];
}
}