C++刷leetcode（322. 零钱兑换）【动态规划】

糖逗

题目描述：

1. 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
   
2. 
   
3.  
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入: coins = [1, 2, 5], amount = 11
   
8. 输出: 3
   
9. 解释: 11 = 5 + 5 + 1
   
10. 示例 2:
    
11. 
    
12. 输入: coins = [2], amount = 3
    
13. 输出: -1
    
14.  
    
15. 
    
16. 说明:
    
17. 你可以认为每种硬币的数量是无限的。
    
18. 
    
19. 来源：力扣（LeetCode）
    
20. 链接：https://leetcode-cn.com/problems/coin-change
    
21. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <vector>
   
3. #include <string>
   
4. #include <algorithm>
   
5. using namespace std;
   
6. 
   
7. 
   
8. int solution(vector<int>& coins, int amount) {
   
9.     if(amount == 0) return 0;
   
10.     vector<int> dp(amount+1, INT_MAX);
    
11.     vector<int> store;
    
12.     for(int i = 0 ;i < coins.size(); i++){
    
13.         if(coins[i] <= amount){
    
14.             store.push_back(coins[i]);
    
15.             dp[coins[i]] = 1;
    
16.         }
    
17.     }
    
18.     for(int i = 1; i <= amount; i++){
    
19.         if(dp[i] == 1) continue;
    
20.         for(int j = 0; j < store.size(); j++){
    
21.             if(i-store[j] >= 0 && dp[i-store[j]] != INT_MAX){
    
22.                 dp[i] = min(dp[i-store[j]]+1, dp[i]);
    
23. 
    
24.             }
    
25.         }
    
26.         
    
27.     }
    
28.     return dp[amount] == INT_MAX ? -1 : dp[amount];
    
29. }
    
30. 
    
31. int main(void){
    
32.         vector<int> input;
    
33.         int number;
    
34.         while(cin >> number){
    
35.                 input.push_back(number);
    
36.         }
    
37.         cin.clear();
    
38.         int amount;
    
39.         cin >> amount;
    
40.         cout << solution(input, amount) << endl;
    
41.         return 0;
    
42. }
    
43. 
    

复制代码