LeetCode: 322. Coin Change

发表于 | 分类于

题目描述

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:

1
2
3
Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

1
2
Input: coins = [2], amount = 3
Output: -1

这题也是一道动态规划的题目。令dp[i]为累积和为i的最小的coin的个数。转移方程为:

含义就是当i在coins里的话，只需要取一个就好了，剩下的情况需要取找之前和i相差coins里的一枚硬币的最小值，然后加一即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0)
            return 0;
        if (coins.size() == 0)
            return -1;
        vector<int> dp(amount+1, -1);
        
        for (int i = 1; i < dp.size(); i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (i-coins[j] == 0) {
                    dp[i] = 1;
                }
                if (i-coins[j] > 0 && dp[i-coins[j]] != -1) {
                    if (dp[i] == -1)
                        dp[i] = dp[i-coins[j]]+1;
                    else
                        dp[i] = min(dp[i], dp[i-coins[j]]+1);
                }
            }
        }
        return dp[dp.size() - 1];

    }
};