这是我自创的一个题目,我也没有在其他地方看到过这样称呼的。
背包计数问题: 求装满背包有几种方法。
求解方法
其实这个求解方法很死:
我们一般用一维dp求解。
递推公式
求装满背包的方法 dp[j] += dp[j - nums[i]]。
初始化
死记: dp[0] = 1,别问
遍历顺序
注意遍历背包和遍历物品的顺序。
有下面两种：
排列问题：先背包再物品，注意内层循环判断背包大于物品。
组合问题：先物品再背包，
记忆方法
排字的右偏旁和背字的上偏旁是一样的,所以排列->先背包再物品
注意遍历背包要是否要倒序就涉及到是01背包还是完全背包。
剖析
其实我们知道解题方法已经可以解题了,例如:
57. 爬楼梯（第八期模拟笔试） (kamacoder.com)
那么为什么？？
排列问题是先背包再物品
而组合问题是先物品再背包。
我先自己猜测一个答案,