leetcode力扣518——零钱兑换 II

力扣518

题目：

• 给你一个整数数组 coins 表现不同面额的硬币，另给一个整数 amount 表现总金额。
  
• 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
  
• 假设每一种面额的硬币有无限个。 
  
• 题目数据保证结果符合 32 位带符号整数。
  

思绪

从题目中能确认的是：
（1）coins中的数能重复利用
（2）以背包的角度看，背包的容量巨细为amount + 1
        可以定义dp(amount + 1, 0)，其中dp[0]=1；dp表现当amount为i时，可以凑成总金额的硬币组合数。
        由于coins中的数能重复利用，那么设先从小物品放起，如果小物品自身就能装满背包，那就结果+1，然后小物品配合更大的物品放置。
看看代码逻辑：

1.         for(int i = 0; i < coins.size(); i++)     //遍历物品
2.         {
3.             for(int j = coins[i]; j <= amount; j++)    //遍历背后
4.             {
5.                 dp[j] += dp[j - coins[i]];
6.             }
7.         }

复制代码

比如说：
  

1.         //举例，amount = 5， coins = {1, 2, 5}                
2.         //初始化 dp = [1, 0, 0, 0, 0, 0]                                
3.         //处理硬币 1：  
4.         //j = 1: dp[1] += dp[0] → dp = [1, 1, 0, 0, 0, 0]  
5.         //j = 2: dp[2] += dp[1] → dp = [1, 1, 1, 0, 0, 0]                
6.         //j = 3: dp[3] += dp[2] → dp = [1, 1, 1, 1, 0, 0]                
7.         //j = 4: dp[4] += dp[3] → dp = [1, 1, 1, 1, 1, 0]                
8.         //j = 5: dp[5] += dp[4] → dp = [1, 1, 1, 1, 1, 1]                                
9.         //处理硬币 2：  
10.         //j = 2: dp[2] += dp[0] → dp = [1, 1, 2, 1, 1, 1]  
11.         //j = 3: dp[3] += dp[1] → dp = [1, 1, 2, 2, 1, 1]                
12.         //j = 4: dp[4] += dp[2] → dp = [1, 1, 2, 2, 3, 1]                
13.         //j = 5: dp[5] += dp[3] → dp = [1, 1, 2, 2, 3, 3]                                
14.         //处理硬币 5：  
15.         //j = 5: dp[5] += dp[0] → dp = [1, 1, 2, 2, 3, 4]  
16.                                 
17.         //最终 dp[5] = 4，表示用 {1, 2, 5} 凑成 5 的方法有 4 种。  

复制代码

代码

第一版

主要的实现逻辑已经出来了，那根本可以写出代码了：

1. #include "iostream"  
2. #include "vector"  
3. using namespace std;  
4.   
5. class Solution  
6. {  
7. public:  
8.     int change(int amount, vector<int> &coins)  
9.     {  
10.         vector<int> dp(amount + 1, 0);  
11.         dp[0] = 1;  
12.         for(int i = 0; i < coins.size(); i++)     //遍历物品  
13.         {  
14.             for(int j = coins[i]; j <= amount; j++)    //遍历背后  
15.             {  
16.                 dp[j] += dp[j - coins[i]];  
17.             }  
18.         }  
19.         return dp[amount];  
20.     }  
21. };

复制代码

最终实现

特殊地，偶数是凑不出奇数的，可以提前把这种情况给排除：

1. #include "iostream"#include "vector"using namespace std;class Solution{public:    int change(int amount, vector<int> &coins)    {        vector<int> dp(amount + 1, 0);        dp[0] = 1;        //偶凑不出奇        bool flag = false;        for(int c : coins)            if(c % 2)  //有奇数                flag = true;        if(!flag && amount % 2)            return 0;        for(int i = 0; i < coins.size(); i++)     //遍历物品
2.         {
3.             for(int j = coins[i]; j <= amount; j++)    //遍历背后
4.             {
5.                 dp[j] += dp[j - coins[i]];
6.             }
7.         }        return dp[amount];    }};

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。