leetcode解题: Coin Change (322)

发表于 | 分类于

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.

解法1：DP, O(N*M), N 是coin的个数，M是amount的数字

用DP来解，因为涉及到了“检验某一种步骤是否可行”。基本思路是假设dp[i]代表的是$i所需要的最少的coins的数目。
因为我们的coins的面额是已知的。那么对每一个coins的面额j
我们可以有如下的关系

1
dp[i + coins[j]] = min(dp[i] + 1, dp[i + coins[j]])

因为dp[i]已知，那么最多的coins就能确定是dp[i] + 1, 直接用下一个可用的coin即可。
然后对于coins的array和从1到i循环，不停的更新dp[i], dp[amount]就是我们要求的数值。
要注意的是，在更新一个dp[i‘]的时候， 要保证dp[i]已知（！=INT_MAX)而且下标不要超界，还有coins[j]也不要超过INT_MAX (不会overflow)
可以用coins[j] <= INT_MAX - i
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;  // initialize the first data point
        for (int i = 0; i <= amount; ++i) {
            for (int j = 0; j < coins.size(); ++j) {
                if (coins[j] != INT_MAX && i + coins[j] <= amount && dp[i] != INT_MAX) {
                    dp[i + coins[j]] = min(dp[i] + 1, dp[i + coins[j]]);
                }
            }
        }
        return dp[amount] == INT_MAX ? -1: dp[amount];
    }
};

Java

1