一般 DP 转移方程

yangfengzhao · 2025-08-05 09:31:03 · 算法·理论

动态规划（DynamIc ProgrammIng，或称 DP）算法通常用于全局求解某种具有最优性质的问题。\ 动态规划算法与分治法类似，其基本思想也是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解中得到原有问题的解。与分治法不同的是，动态规划经分解后得到的子问题往往不是相互独立 的。

1. 常见的线性 DP（LInear DP）

这应该是最简单的 DP 模型了。这个模型用于解决所有呈线性的状态转移的 DP。 :::Info[符号说明]

1.2 LNDS 最长不降子序列

一般性的问题：求序列中非递减的最长子序列（允许相等元素）。\ 状态定义：{Dp[I]} 表示以第 {I} 个元素结尾的最长不降子序列长度。\ 转移方程：

1.3 LNIS 最长不升子序列

一般性的问题：求序列中非递增的最长子序列（允许相等元素）。\ 状态定义：{Dp[I]} 表示以第 {I} 个元素结尾的最长不升子序列长度。\ 转移方程：

1.4 LCS 最长公共子序列

一般性的问题：求两个序列的最长公共子序列（元素不要求连续）。\ 状态定义：{Dp[I][J]} 表示序列 A 前 {I} 个元素与序列 B 前 {J} 个元素的最长公共子序列长度。\ 转移方程：{Dp[I][J] = \begin{cases} Dp[I-1][J-1] + 1 & SeqThIs[I-1] = SeqOthr[J-1] \\ \max(Dp[I-1][J], Dp[I][J-1]) & SeqThIs[I-1] \neq SeqOthr[J-1] \end{cases}}\ 初始值：{ \begin{cases} Dp[I][0] = 0 & \forall 0 \leq I \leq SqLth_A \\ Dp[0][J] = 0 & \forall 0 \leq J \leq SqLth_B \end{cases}}\ 结果：

2. 常见的背包 DP（Knapsack DP）

也是最常见的 DP 模型，用于解决贪心不能解决的在有限容量下选择物品以获得最优的问题。（下列叙述将仅叙述其特征！） :::Info[符号说明]

实现时需要注意：逆推 + 滚动数组会更优！

2.2 ON 背包（完全背包）

::::success[题外话] 0N 背包是因为机房里有很多人喜欢写这样子的代码：

const Int N=0x7f7f7f7f;

而这个数很大，可以说是无穷大（对于 Int 来说）。而完全背包又刚刚好对应的下面的要素。 :::: 特征要素：

• 每件物品有无数样

  那么考虑：设 {Dp[I][J]} 表示选择（多样或不选）前 {I} 个物品在占用不超过 {J} 容量时的最大的价值。\ 思路：由于有无限个物品，所以需要考虑第 {I} 个物品选择 {K} 个最合适。同样，{Dp[I][J]} 的设定同上。

  1. 选 {K} 件第 {I} 件物品，则此时的 {Dp[I][J]=Dp[I-1][J-K*W_{I}]+K*V_{I}}，当然，不能超过背包容量 {Cap}；
  2. 不选，就是 {Dp[I][J]}。 此时，状态转移方程就是： Dp[I][J]=\max \begin{cases} Dp[I][J],\\ Dp[I-1][J-K*M_{I}]+K*V_{I} \end{cases} }

  3. 当然，由于三重循环可能会爆 TLE，所以在实现时可以考虑每次比上次多选一件或不选，再取最大值。

     实现时需要注意：顺推 + 滚动数组会更优！

     2.3 0C 背包（多重背包中的有限数量背包）

     ::::success[还是题外话] 0C 背包是因为定义的 {C_{I}} 表示的是其数量。 :::: 特征要素：

• 每件物品有 {C_{I}} 样

  那么考虑：设 {Dp[I][J]} 表示选择（不超过 {C_{I}} 样或不选）前 {I} 个物品在占用不超过 {J} 容量时的最大的价值。\ 思路一（从完全背包推演）：由于只有 {C_{I}} 个物品，所以需要考虑第 {I} 个物品选择 {K (\leq C_{I})} （下文的 {K} 同理）个最合适。同样，{Dp[I][J]} 的设定同上。

  1. 选 {K} 件第 {I} 件物品，则此时的 {Dp[I][J]=Dp[I-1][J-K*W_{I}]+K*V_{I}}，当然，不能超过背包容量 {Cap}；
  2. 不选，就是 {Dp[I][J]}。 此时，状态转移方程就是： Dp[I][J]=\max \begin{cases} Dp[I][J],\\ Dp[I-1][J-K*M_{I}]+K*V_{I} \end{cases} }

  3. 当然，由于三重循环可能会爆 TLE，所以在实现时可以考虑每次比上次多选一件或不选，再取最大值。

     思路二（从 01 背包推演）：将每个有限件的物品拆开成单个独立的物品。然后套 01 背包。

  4. 需要优化：因为这样相当于二进制选择，而其会出现很多种重复的方案。所以考虑倍增（二次幂）优化：将一个物品拆成这样的序列：{[1,2,...,C_{I}-2^{N}(C_{I} \geq 2^{N})]}，然后将价值和重量套回去就可以了！

  5. 请注意：对于高次幂的物品倍增方法（如果 {Byte \geq 10}，那就会适得其反），因为每增加一个进制单位，就会冗余一个单件的物品（除非你刚刚好是某个进制的前几项的和），反而会效果变差。

     实现时：用 01 背包就可以了。（单调 Que 还不会，我太蒟了）

     3. 常见的区间 DP（Interval DP）

     这算一个线性 DP 的扩展版。 :::Info[符号说明]

     ${Seq_{I}}$ = 序列的第 ${I}$ 个元素；\ ${Vl_{J}}$ = 序列的第 ${J}$ 在合并后的价值； :::: **一般性的问题**：在一个序列中合并相邻的两个元素使得其价值最优。\ **状态定义**：${Dp[I][J]}$ 表示序列在合并 ${I}$ 和 ${J}$ 两堆时最优。\ **思路**：因为是要合并两堆，所以会是合并于子序列 ${[I,K]}$ 和 ${[K+1,J]}$ 的最优值。既然是要取最优值，就要遍历所有可能的 ${K \in [I,J]}$。注意到若 ${I=J}$ 时，价值是固定的（提前处理价值 ${Vl}$）。\ **转移方程**：${Dp[I][J] = Dp[I][K] + Dp[K+1][J] + (Vl[I]|Vl[J]|Vl[I+J])}

     初始值：{Dp[I][I] = Vl[I]}\ 结果：

     {Dp[I][J]}

     4. 常见的树形 DP（Tree DP）

     5. 常见的状压 DP（State Compression DP）

     6. 记忆化 DFS（MemoizatIon DFS）

     7. 记忆化 BFS（MemoizatIon BFS）