322. Coin Change

发表于 | 分类于

每日一题 2019 - 02 - 27

题目：

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

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

解法：

这个题为动态规划的题，得到的递推公式为：

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

当零钱为i元需要的最少硬币数等于第i元减去硬币中所有出现的可能的小于i元的硬币的出现次数加1，这里的j从0循环到coins.size()-1。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
	int *dp = new int[amount + 1,amount+1];
        for(int i=1;i<=amount;i++){
            dp[i]=(amount+1);
        }
	dp[0] = 0;
	int res = -1;
	for (int i = 1; i <= amount; i++) {
		for (int j = 0; j < coins.size(); j++) {
			if (i -coins[j]>=0) {
				dp[i] = min(dp[i], dp[i - coins[j]] + 1);
			}
		}
	}
        res = (dp[amount] == (amount + 1))? -1 : dp[amount];  
	delete[] dp;
    return res;
    }
};
0%
undefined