518. 零钱兑换 II

 1 class Solution 
 2 {
 3 public:
 4     //完全背包问题
 5     int change(int amount, vector<int>& coins) 
 6     {
 7         vector<int>dp(amount + 1,0);
 8         dp[0] = 1;
 9         for(int i = 0;i < coins.size();i ++)//背包种类
10         {
11             for(int j = coins[i];j <= amount;j ++)//背包容量
12             {
13                 dp[j] = dp[j] + dp[j - coins[i]];//能选一定选，即含有贪心思路，就写 "+"
14                                                  //可以选也可以不选，就写 "max"
15             }
16         }
17         return dp[amount];
18     }
19 };