第一阶段复习——基础动态规划

背包知识点总结：

1. 01背包、完全背包的转移方程
2. 滚动数组和倒序
3. 初始化问题：完全放满和不一定放满
4. 多重背包二进制优化，边界问题。处理完之后跑完全背包。“在这一讲中，我们看到了将一个算法的复杂度由 O(V ΣMi) 改进到 O(V ΣlogMi) 的过程，还知道了存在复杂度为 O(V N) 的算法。 ”单调队列仍不会
5. 二维费用背包，仍可以套用01或完全的思路，滚动数组、辅助数组或者逆序
6. 01背包方案数和最优方案数，dx
7. 小优化：费用高还价值低的物品，可以删去。
8. 有依赖的背包问题
9. 泛化物品

参考：背包问题九讲。

有依赖的背包问题：金明的预算方案。

更一般地，附件也可以有自己的附件，这样就构成了森林，需要树形dp。