吃奶酪
最小异或值之和
动态规划与背包专题笔记
一、数字三角形
状态
dp[i][j]：从 (1,1) 出发走到 (i,j) 能得到的最大路径和。
转移
代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、01 背包——最大价值
1. 二维 DP
状态
表示：
> 前 i 个物品，背包容量不超过 j 时的最大价值。
对于第 i 个物品：
所以：
二维代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 一维优化
观察：
只会使用：
所以第一维可以删掉。
为什么倒序？
二维中：
不能参与转移，必须使用：
所以一维时从大到小更新，保证 dp[j-w] 还是上一层。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、01 背包——方案数
1. 二维 DP
状态
dp[i][j]：
> 前 i 个物品，恰好凑出重量 j 的方案数。
第 i 个物品：
所以：
初始化
二维代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 一维优化
还是倒序：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、完全背包——最大价值
每种物品可以使用无限次。
1. 二维 DP
状态
dp[i][j]：
> 前 i 种物品，容量不超过 j 时的最大价值。
不选第 i 种：
选择第 i 种：
注意这里和 01 背包不同：
因为当前物品还能继续选。
转移
二维代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 一维优化
为什么正序？
因为二维转移本来就是：
也就是允许使用当前这一层刚刚算出的状态。
所以：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、装箱问题
本质：
每件物品只能使用一次，所以是 01 背包。
1. 二维 DP
状态
dp[i][j]：
> 前 i 个物品，容量不超过 j 时最多能够装入多少体积。
转移
二维代码
存在性01背包
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 一维优化
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、摆花——有限数量方案数
第 i 种花最多放 a[i] 盆。
1. 二维 DP
状态
dp[i][j]：
> 前 i 种花，一共摆 j 盆的方案数。
第 i 种花可以摆：
所以：
二维代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 一维优化
这里也可以压成一维。
因为当前第 i 种花最多只能使用 a[i] 次，所以容量要倒序。
这里：
对应第 i 种花放 0 盆。
然后：
对应第 i 种花摆 k 盆。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、多重背包
每种物品：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 二维 DP
状态
dp[i][j]：
> 前 i 种物品，容量不超过 j 时能够获得的最大价值。
第 i 种物品可以选：
所以：
二维代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 一维优化
删掉第一维以后：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. A7934 最长上升子序列
状态：
复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. A20908 石子合并
典型 区间 DP。
状态：
枚举最后一次在哪里分开：
转移：
代码：
复杂度：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. U48931 打家劫舍
相邻房屋不能同时选择。
状态：
第 i 间房：
所以：
代码：
1. T112030 双重限制藏宝计划
这是 二维费用 01 背包：
核心：
表示：
> 体积不超过 j、重量不超过 k 时的最大价值。
因为每件宝藏只能选一次，所以两个容量都要倒序：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. T112033 哥布林的秘宝密码
这是标准 最长公共子序列 LCS。
状态：
表示：
> 字符串 a 前 i 个字符和字符串 b 前 j 个字符的最长公共子序列长度。
如果：
说明两个字符可以同时接上：
否则只能舍弃其中一个：
二进制枚举
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
状压 DP：最小异或值之和
1. 核心问题
每个 a[i] 要匹配一个不同的 b[j]，目标是：
最小。
本质就是：
> 每次给当前 a[i] 选一个还没用过的 b[j]。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 状态表示
表示：
> 已经使用了状态 s 中这些 b 后，最小异或和。
例如：
表示：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 当前处理哪个 A
cnt 就是已经用了多少个 b。
因此前面已经匹配了：
当前处理：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 枚举一个没用过的 B
判断：
说明 b[j] 还没使用。
把它加入：
转移：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 初始化和答案
表示一个 b 都没选，代价为 0。
其他状态：
最终所有 b 都使用：
就是答案。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 核心代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 一句话理解
所以状压 DP 本质就是：
> 用二进制状态记录“哪些东西已经选过”，代替全排列。
复杂度：
