目录

• 背包问题（一维数组形式）

  • 做题逻辑

  • 01背包

    • 1. 遍历背包容量时为什么要逆序？
    • 2. 为什么二维形式的遍历背包容量时不用逆序？
    • 3. 必须先物品循环在外，背包循环在内

  • 完全背包

    • 1. 遍历背包容量时为什么要正序？
    • 2. 对于纯完全背包问题（求背包最大/最小总价值），哪个循环在外哪个循环在内，都可以
    • 3. 求装满背包有几种方案的时候，要考虑谁是外循环谁是内循环

  • 递归公式总结

• 打家劫舍

• 股票问题

背包问题（一维数组形式）

做题逻辑

01背包

1. 遍历背包容量时为什么要逆序？

    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

2. 为什么二维形式的遍历背包容量时不用逆序？

图中例子，dp[6]=max(dp[6],dp[6-3]+5)；出错原因是，如果顺序遍历，dp[3]已经更新为包含物品1的情况，但二维数组中递推公式是，dp[i] [j]=max (dp[i - 1] [j] + dp[i - 1] [j - weight[i]] + value[i])；dp[1][3]更不更新都没关系，因为dp[1][6]找的是dp[0][3]

3. 必须先物品循环在外，背包循环在内

原因：我们说 二维的遍历顺序，可以是按行从上往下，也可按列从左往右，因为每个数据只和他的左上数据有关； 对于一维，如果是背包在外，物品在内，就相当于是二维的按列从右往左遍历，这样肯定不行

完全背包

1. 遍历背包容量时为什么要正序？

这里与01背包正好相反，完全背包要求物品重复利用，所以正序是为了使物品可以被多次取拿

2. 对于纯完全背包问题（求背包最大/最小总价值），哪个循环在外哪个循环在内，都可以

因为它的背包容量遍历是顺序的，所以物品循环在外，背包在内，就相当于二维的，按行从上到下遍历；反之，就是按列，从左到右遍历

3. 求装满背包有几种方案的时候，要考虑谁是外循环谁是内循环

• 组合不强调元素之间的顺序，排列强调元素之间的顺序

• （硬币在外，金额在内）拿到一个硬币A，看能怎么组合成各个金额，再来一个硬币B，要？{A..}+B；不要？{A..}；B总在A后面拿到，所以不会有{B，A}的组合情况

• （金额在外，硬币在内）对于每个金额的取得，dp[j]都是考虑过所有硬币的 假如{B}得到dp[1]，对dp[2]又要重新考虑各个硬币要还是不要；要？dp[2]=dp[2-1]+1（设A=1）则排列变为{B}+A；就是说B可能出现在A的后面；即{1，5}和{5，1}都有

• 戳~具体见

递归公式总结

修正：就算是可重复的，每次取一个，它的价值还是算为1（T279.完全平方数）

补充:求最小个数时，往往需要先讲dp数组中元素赋值为最大整数-1（避免溢出），不然默认初始值为0，会导致错误 （T322、279）

打家劫舍

股票问题