动态规划

DP理解方式

状态表示 f[i] f[i][j]

集合 ： 所有选法

1. 只从前 i 个中选择 （一个选择区间）
2. 总体积小于

属性 ：最大值 最小值 数量 等

状态计算

集合的划分 划分成更小的子集 并从子集中计算过来（不重 不漏）

优化方式一般是对状态转移方程做等价变形

背包问题

容量有限 价值最大

1. 01背包 每个物品最多只能用一次
2. 完全背包 每件物品能无限用
3. 多重背包 每个物品数量不一样
4. 分组背包 每组只能选一个物品