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