C++刷LeetCode（518. 零钱兑换 II）【动态规划*】

糖逗

题目描述：

1. 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 
   
2. 
   
3.  
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入: amount = 5, coins = [1, 2, 5]
   
8. 输出: 4
   
9. 解释: 有四种方式可以凑成总金额:
   
10. 5=5
    
11. 5=2+2+1
    
12. 5=2+1+1+1
    
13. 5=1+1+1+1+1
    
14. 示例 2:
    
15. 
    
16. 输入: amount = 3, coins = [2]
    
17. 输出: 0
    
18. 解释: 只用面额2的硬币不能凑成总金额3。
    
19. 示例 3:
    
20. 
    
21. 输入: amount = 10, coins = [10]
    
22. 输出: 1
    
23.  
    
24. 
    
25. 注意:
    
26. 
    
27. 你可以假设：
    
28. 
    
29. 0 <= amount (总金额) <= 5000
    
30. 1 <= coin (硬币面额)&#160;<= 5000
    
31. 硬币种类不超过 500 种
    
32. 结果符合 32 位符号整数
    
33. 
    
34. 来源：力扣（LeetCode）
    
35. 链接：https://leetcode-cn.com/problems/coin-change-2
    
36. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int change(int amount, vector<int>& coins) {
   
4.         //动态规划
   
5.         int len = coins.size();
   
6.         vector<int> dp(amount + 1, 0);
   
7.         dp[0] = 1;
   
8.         for(int j = 0; j < len; j++){//注意顺序
   
9.             for(int i = 1; i <= amount; i++){
   
10.                 if(i - coins[j] >= 0)dp[i] += dp[i-coins[j]];
    
11.             }
    
12.         }
    
13.         return dp[amount];
    
14.     }
    
15. };

复制代码

参考链接：https://leetcode-cn.com/problems ... i-wen-ti-dao-di-yo/

糖逗

建议看一下参考链接