Coin Change (M)
題目
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:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.
題意
選數量最少的硬幣，使其和為amount，
思路
動態規劃，由區域最優解求得全域最優解：設F(N)為和為N的硬幣的最小個數，C為某一硬幣的面值，那么很容易得到 F(N) = F(N - C) + 1，那么只要求得F(N - C)的最小值，就能得到F(N)的最小值，
代碼實作
Java
記憶化
class Solution {
public int coinChange(int[] coins, int amount) {
return dfs(coins, amount, new int[amount + 1]);
}
private int dfs(int[] coins, int remain, int[] record) {
if (remain < 0) {
return -1;
}
if (remain == 0) {
return 0;
}
if (record[remain] != 0) {
return record[remain];
}
int min = Integer.MAX_VALUE;
for (int coin : coins) {
int count = dfs(coins, remain - coin, record);
if (count >= 0 && count + 1 < min) {
min = count + 1;
}
}
record[remain] = min == Integer.MAX_VALUE ? -1 : min;
return record[remain];
}
}
動態規劃
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i >= coin) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/36567.html
標籤：其他