题目描述：

零钱兑换Ⅰ中，所求为凑满总金额需要最少的硬币个数

类似于目标和那道题，只不过那题是01背包问题（遍历顺序为从后往前），这题为完全背包问题

方法1：完全背包问题

本题和纯完全背包问题不同，纯完全背包考虑的是最大价值，所以不用管遍历顺序，本题是求装满的方式总数，得考虑题目要求是排列数还是组合数

考虑coins=[1,2],amount=3的情况

组合数：先遍历物品，再遍历背包，最后一轮涉及3的只有只有dp[3-2]

for (int i = 0; i < coins.size(); i++) { // 遍历物品
    for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
        dp[j] += dp[j - coins[i]];
    }
}

排列数：先遍历背包，再遍历物品，最后一轮涉及3的有dp[3-2]与dp[3-1]

for (int j = 0; j <= amount; j++) { // 遍历背包容量
    for (int i = 0; i < coins.size(); i++) { // 遍历物品
        if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
    }
}

本题为考虑组合数：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int>dp(amount+1,0);
        dp[0] = 1;
        for(int i=0;i<coins.size();i++){
            for(int j=coins[i];j<=amount;j++){
                dp[j] += dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};