【代码随想录|完全背包问题】

518.零钱兑换||

题目链接：518. 零钱兑换 II - 力扣（LeetCode）
这里求的是组合数，就是不强调元素排列的顺序，211和121是同一个数那种，要先遍历物品，这样的话我算出来的每个值才是按顺序121，不会出现211的情况，而我先遍历背包的话，我要达到这个背包数，就要不断尝试

  1、确定dp数组以及下标的含义

dp[j]：凑成总金额j的货币组合数为dp[j]

  2、确定递推公式

我觉得这里的递推公式是这么来的，比如拿dp[5]来说

一、第一次放物品，想要装满，可以往里面放dp[4]，因为1+dp[4]（这时候值为1）刚好装满

二、第二次放物品，想要装满，可以往里面放dp[3]，因为2+dp[3]（这时候值为2）刚好装满

三、第三次放物品，想要装满，可以往里面放dp[0]，因为5+dp[0]（这时候值为1）刚好装满

那我们一共有多少种方法可以到dp[5]呢，就是dp[4]+dp[3]+dp[0]（1+2+1）为4 刚好装满

就是这里的dp[5]如果只看放入第三个物品单从一维来的话5+dp[0]你怎么看dp[0]都是不可能等于4的，所以如果从二维来看，这里的递推公式其实是在纵向不断累加我要达到该值的方法。

3、dp数组如何初始化

dp[0]为1，因为如果dp[0] = 0 的话，后面所有推导出来的值都是0了。

4、确定遍历顺序

这里先遍历物品再遍历背包得到是组合数，就是121和112是同一个

先遍历背包再遍历物品得到的时排序数，121和112是两个数

dp[j]一定是来自于外层上一次的结果，而外层上一次的结果一定是来源于上一个物品的dp数组，也就是只会出现【物品1，物品1，物品2】这种情况，而物品2不会出现在物品1之前，恰好对应组合问题； 而外层遍历背包内层遍历物品就不一样了，每一层的dp[j]都是在固定j的情况下，把物品从头开始遍历，所以dp[j]来自于上一层的结果，而上一层的结果又遍历了所有物品，所以这种遍历方式会出现【物品1，物品2，物品1】这种情况，恰好对应了排列问题

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];
    }
};

总结： 

装满这个背包的最大价值是多少/能不能装满这个背包类的题，先遍历物品和先遍历背包没有影响

装满这个背包有多少种方法类的题，先遍历物品和后遍历背包是组合数，先遍历背包后遍历物品时排列数

377.组合总和|V

题目链接:377. 组合总和 Ⅳ - 力扣（LeetCode）

这道题跟上道题基本一样，就是这道题是排列遍历顺序，上一道是组合的遍历顺序

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int>dp(target+1,0);
        dp[0]=1;
        for(int i=0;i<=target;i++){
            for(int j=0;j<nums.size();j++){  
                if(i-nums[j]>=0)              
                dp[i]+=dp[i-nums[j]];//因为i是遍历背包，j是遍历物品
            }
        }
        return dp[target];
    }
};

70.爬楼梯

题目链接：57. 爬楼梯（第八期模拟笔试）

跟组合组合||差不多，有n个楼梯，每次最多走m个楼梯，那就是背包里的物品是[1,m]，然后我排列的进行选择，选到target看有多少种方法
这里的背包物品是从1到m进行遍历的，所以递归公式里面的是dp[i]+=dp[i-j];

using namespace std;
#include<iostream>
#include<vector>
int main(){
    int n,m;//n是背包容量,m是物品
    cin>>n>>m;
    vector<int> dp(n+1,0);
    dp[0]=1;
    for(int i=0;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i-j>=0)
            dp[i]+=dp[i-j];
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}