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 =

return

coins =

`[1, 2, 5]`

, amount = `11`

return

`3`

(11 = 5 + 5 + 1)
Example 2:

coins =

return

coins =

`[2]`

, amount = `3`

return

`-1`

.
Note:

You may assume that you have an infinite number of each kind of coin.

You may assume that you have an infinite number of each kind of coin.

**Understand the problem:**

The problem is a backpack problem. Each item can be selected unlimited number of times. Ask what is the minimum picks in order to fulfill the target amount. We can solve it using DP.

-- dp[n + 1][amount + 1], where dp[i][j] means the minimum number of coins in the first i coins for which the sum of amount equal to j.

-- Initialization:

dp[0][0] = 0;

dp[0][j] = Integer.MAX_VALUE, means there is no way to fulfill the amount j with no coins

dp[i][0] = 0, meaning the number of coins is 0 to meet the total amount 0.

For others, the initial state is Integer.MAX_VALUE.

**Code (Java):**

public class Solution { public int coinChange(int[] coins, int amount) { if (coins == null || coins.length == 0 || amount <= 0) { return 0; } int n = coins.length; int[][] dp = new int[n + 1][amount + 1]; // initilization for (int i = 1; i <= amount; i++) { dp[0][i] = Integer.MAX_VALUE; } for (int i = 1; i <= n; i++) { for (int j = 0; j <= amount; j++) { dp[i][j] = Integer.MAX_VALUE; for (int k = 0; k * coins[i - 1] <= j; k++) { if (dp[i - 1][j - k * coins[i - 1]] != Integer.MAX_VALUE) { dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k * coins[i - 1]] + k); } } } } if (dp[n][amount] == Integer.MAX_VALUE) { return -1; } else { return dp[n][amount]; } } }

**A O(amount) space solution:**

Since dp[i] only depends on dp[i - 1], we can simply reduce the space complexity to O(amount).

**Code (Java):**

public class Solution { public int coinChange(int[] coins, int amount) { if (coins == null || coins.length == 0 || amount <= 0) { return 0; } int[] dp = new int[amount + 1]; for (int i = 1; i <= amount; i++) { dp[i] = Integer.MAX_VALUE; } for (int i = 1; i <= amount; i++) { for (int j = 0; j < coins.length; j++) { if (coins[j] <= i) { if (dp[i - coins[j]] != Integer.MAX_VALUE) { dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1); } } } } if (dp[amount] == Integer.MAX_VALUE) { return -1; } else { return dp[amount]; } } }

## No comments:

## Post a Comment