线性 DP、背包问题、区间 DP 学习笔记

动态规划基础知识

基本概念

1. 动态规划：解决多阶段决策过程最优化问题的一种方法。
2. 阶段：把问题分解成相互联系的有顺序的几个环节，这些环节即成为阶段。
3. 状态：某一阶段的出发位置称为状态。通常一个阶段包含若干状态。
4. 决策：从某阶段的一个状态演变到下一个阶段某状态的选择。
5. 策略：由开始到终点的全过程中，由每段决策组成的决策序列称为全过程策略，简称策略。
6. 状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由阶段 \(i\) 到 \(i+1\) 阶段状态的演变规律，称为状态转移方程。

基本原理

1. 乘法原理与加法原理

基本条件

1. 具有形式相同的子问题。
2. 满足最优子结构，即问题的最优解包含着子问题的最优解，不管前面的策略如何，此后的决策必须是基于当前状态(由上一次决策产生)的最优决策。
3. 满足无后效性。动态规划只适用于解决当前决策与过去状态无关的问题，故必须选择恰当的状态参量。

基本步骤

1. “我是谁？我在哪？”——结合原问题与子问题确定状态。搞清题目在求什么，求出这个值需要什么，什么是影响答案的因素。
2. “我从哪里来？/我到哪里去？”——确定状态转移方程。确定当前状态是否满足基本条件，从上一阶段如何转移过来，初始化。
3. 考虑优化以及实现方式（递推、记忆化搜索）。

背包问题

1. 01 背包

1. 基本问题：有 \(N\) 件物品和一个容量为\(V\) 的背包。第 \(i\) 件物品的费用是 \(c_i\)，价值是 \(w_i\)。求解将哪些物品装入背包可使价值总和最大，输出价值最大值。

2. 完全背包

1. 基本问题：有 \(N\) 种物品和一个容量为 \(V\) 的背包，每种物品都有无限件可用。放入第 \(i\) 种物品的费用是 \(c_i\)，价值是 \(w_i\).求解:将哪些物品装入背包，可使这些物品的耗费的费用总和不超过背包容量，且价值总和最大。
2. 解决方式：正向滚动。

3. 多重背包

1. 基本问题：有 \(N\) 种物品和一个容量为 \(V\) 的背包。第 \(i\) 种物品最多有 \(n_i\) 件可用，每件费用是 \(c_i\)，价值是 \(w_i\)。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
2. 解决方式：通过二进制将 \(n_i\) 个第 \(i\) 种物品转化为若干件物品，使得第 \(i\) 件物品的选取策略（\(0\) 到 \(n_i\) 件）均可以实现，且不会出现超过 \(n_i\) 件的选取策略。如当 \(n_i=22\) 时，可将去转化为分别由 \(1\)、\(2\)、\(4\)、\(8\)、\(7\) 件第 \(i\) 种物品捆绑而来的 \(5\) 个等价物品。

4. 二维费用的背包问题

1. 基本问题：对于每件物品，具有两种不同的费用；选择这件物品必须同时付出这两种代价；对于每种代价都有一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。
2. 解决方式：再添一维即可。
3. 启示：当发现问题是由熟悉的动态规划题目添加了限制条件变形时，可尝试增加状态维数以满足限制条件。

5. 分组背包

1. 基本题型：有 \(N\) 件物品和一个容量为 \(V\) 的背包。第 \(i\) 件物品的费用是 \(c_i\)，价值是 \(w_i\)。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
2. 解决方式伪代码：

for k from 1 to K:// K 为组数。
	for v from V to 0:
		for i in son[k]:// son[k]为属于第 k 组的元素集合。
			f[v]=max(f[v],f[v-c[i]]+w[i])// f_{i,v} 表示在前 i 组中选，背包容量为 v，所能获得的最大价值。

推荐读物——《背包九讲》

初级处理技巧与优化

1. 时间优化：bitset 优化、前缀和、前缀最值。
2. 空间优化：bitset 优化、转移零点，在转移过程中忽略不可能成为答案的状态——如：背包容积大但获得的价值小、通过分析得出某状态参量实际值远小于题干的极限数据、发现路径有周期性（路径可压缩），用 map 动态存可能成为答案的状态。
3. 处理环状问题的两种方式：区间 DP，可采用将相同序列拼接在原序列尾部；线性 DP，一般情况下不可采取将相同序列拼接在尾部的策略，因为可能导致某一位置的值被重复调用，故可分为原序列，以及某一区间从 \(n\) 跨到 \(1\) 后某数两种情况讨论。特别地，对于跨过的区间，分为开头必须为 \(1\) 的区间和结尾必须为 \(n\)的区间。