1.明确定义的dp数组的含义
2.找到递推公式
在递推公式中我有以下总结
一、斐波那契数列，爬楼梯的递推公式为dp[i]=dp[i-1]+dp[i+2],种类问题
二、不同路径问题：规定走的方向，dp[i][j]=dp[i][j-1]+dp[j-1][i](左下)
三、整数拆分，dp[i]=j*dp[i-j]初始化dp[2]=1，第一层for循环从i=3开始j从1开始j<i
四、不同的二叉搜索树，dp[i]+=dp[j-1]*dp[i-j]左子树*右子树从j=1到i累加
五、0-1背包dp[j]=max(dp[j-weight[i]]+value[i],dp[j]);先物品,后背包且背包倒叙（保证了每次加一次物品），，，有类似的问题分割等和子集，最后一块石头相撞，
装满背包有多少种方法dp[j]+=dp[j-nums[i]];dp[0]=1;
升级版（两个维度）一和零（10,001,01）要求装满i个1与j个0的容器最多的子集数 这里定义dp[i][j]表示装i与j的最多个数0-1背包问题
dp[i][j]=max(dp[i][j],dp[i-w0[x]][j-w1[j]]+1);先物品，后背包，倒叙背包
六、完全背包问题,可以多次放入物品，这里使用先物品后背包，在背包中使用正序遍历for(int j=weight[i],j<backge;j++)
模拟重量为一的放入次序可以理解
这里的例题为零钱兑换（1,2,3）兑换为5,这里没有强调顺序，可以多次使用，就是一个完全背包问题，则dp[j]+=dp[j-nums[i]]顺序为先物品后背包（组合问题）
3.初始化
4.遍历顺序
5.打印检查
今天先总结到这里
标签：感悟,背包,weight,递推,问题,物品,动态,规划,dp From： https://www.cnblogs.com/zhangmingmkzj/p/18122479