背包型

01背包：要么选1个，要么不选

多重背包：可选多份

完全背包：可以分分割（贪心法，不是DP）

其他DP没有维度是和的DP，所以背包问题是很特殊的DP

第一种状态表示

dp[i][j]表示前i个物品，是否可以表示出总和j

第二种状态表示

dp[i][j]表示前i个物品，挑出<=j的最大和是多少

效率比第一种低，原因：或运算比+快

背包问题小结

通常是二维的状态数组，前i个组成和为j

状态数组的大小需要开(n + 1)* (m + 1)

题目中通常有“和”与“差”的概念，数值会被放到状态中

每个数存在选或者不选两种状态（01背包）

每个数可以选任意多个（多重背包）

数的顺序无关

01背包的三种变形

最小划分

划分成两部分，使得相差最小

可以抽象成背包容量sum/2的01背包Onn

|SUM - X - X| = |SUM - 2X|最小，最接近SUM/2

外卖优惠券

每种商品只能购买一次，最少买多少钱，可以用上满x优惠的优惠券

大于等于X的最小值 = SUM - 小于等于X的最大值

背包容量SUM - X

石头碰撞

腾讯的题

两个石头a, b，碰撞完以后变成一个石头|a-b|，直到石头数量<2，求最后剩下的石头最小是多少

= 最小划分

可以看做最小划分的两个木桶，每次碰撞就把下面砍掉一个底