一般 DP 转移方程

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

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

这应该是最简单的 DP 模型了。这个模型用于解决所有呈线性的状态转移的 DP。

符号说明

{SqLth}

= 序列总长度；

{Dp}

= 动态规划状态数组；

{AsLth}

= 所求子序列长度；

{SeqThIs}

= 原始序列（索引从

{0}

开始）；

{SeqOthr}

= 其他序列（同理，在 LCS 等会用到）；

1.1 LIS 最长上升子序列

一般性的问题：求序列中严格递增的最长子序列长度（元素不要求连续）。
状态定义：

{Dp[I]}

表示以第

{I}

个元素结尾的最长上升子序列长度。
转移方程：

{Dp[I] = \max\limits_{\substack{0 \leq J < I \\ SeqThIs[J] < SeqThIs[I]}} \{ Dp[J] \} + 1}

初始值：

{Dp[I] = 1 \quad (\forall 0 \leq I < SqLth)}

结果：

{AsLth = \max\limits_{0 \leq K < SqLth} Dp[K]}

1.2 LNDS 最长不降子序列

一般性的问题：求序列中非递减的最长子序列（允许相等元素）。
状态定义：

{Dp[I]}

表示以第

{I}

个元素结尾的最长不降子序列长度。
转移方程：

{Dp[I] = \max\limits_{\substack{0 \leq J < I \\ SeqThIs[J] \leq SeqThIs[I]}} \{ Dp[J] \} + 1}

初始值：

{Dp[I] = 1 \quad (\forall 0 \leq I < SqLth)}

结果：

{AsLth = \max\limits_{0 \leq K < SqLth} Dp[K]}

1.3 LNIS 最长不升子序列

一般性的问题：求序列中非递增的最长子序列（允许相等元素）。
状态定义：

{Dp[I]}

表示以第

{I}

个元素结尾的最长不升子序列长度。
转移方程：

{Dp[I] = \max\limits_{\substack{0 \leq J < I \\ SeqThIs[J] \geq SeqThIs[I]}} \{ Dp[J] \} + 1}

初始值：

{Dp[I] = 1 \quad (\forall 0 \leq I < SqLth)}

结果：

{AsLth = \max\limits_{0 \leq K < SqLth} Dp[K]}

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}}

结果：

{AsLth = Dp[SqLth_A][SqLth_B]}

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

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

符号说明

{\texttt{Cap}}

= 背包容量；

{Dp}

= 动态规划状态数组；

{V_{T}}

= 第

{T}

件物品的价值；

{M_{T}}

= 第

{T}

件物品的重量（代价）；

{C_{T}}

= 第

{T}

件物品的数量；

2.1 01 背包

特征要素：

每件物品只有 ${1}$ 样

那么考虑：设

{Dp[I][J]}

表示选择（单样或不选）前 ${I}$ 个物品在占用不超过 ${J}$ 容量时的最大的价值。
思路：考虑打擂台（选最优嘛）。

选第 ${I}$ 件物品，则此时的 ${Dp[I][J]=Dp[I-1][J-W_{I}]+V_{I}}$ ；
不选，就是 ${Dp[I][J]}$ 。此时，状态转移方程就是： ${ Dp[I][J]=\max \begin{cases} Dp[I][J],\\ Dp[I-1][J-M_{I}]+V_{I} \end{cases} }$

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

2.2 ON 背包（完全背包）

题外话

0N 背包是因为机房里有很多人喜欢写这样子的代码：

CPP

const Int N=0x7f7f7f7f;

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

特征要素：

每件物品有无数样

那么考虑：设

{Dp[I][J]}

表示选择（多样或不选）前 ${I}$ 个物品在占用不超过 ${J}$ 容量时的最大的价值。
思路：由于有无限个物品，所以需要考虑第

{I}

个物品选择

{K}

个最合适。同样，

{Dp[I][J]}

的设定同上。

选 ${K}$ 件第 ${I}$ 件物品，则此时的 ${Dp[I][J]=Dp[I-1][J-K*W_{I}]+K*V_{I}}$ ，当然，不能超过背包容量 ${Cap}$ ；
不选，就是 ${Dp[I][J]}$ 。此时，状态转移方程就是： ${ Dp[I][J]=\max \begin{cases} Dp[I][J],\\ Dp[I-1][J-K*M_{I}]+K*V_{I} \end{cases} }$
当然，由于三重循环可能会爆 TLE，所以在实现时可以考虑每次比上次多选一件或不选，再取最大值。

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

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

还是题外话

0C 背包是因为定义的

{C_{I}}

表示的是其数量。

特征要素：

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

那么考虑：设

{Dp[I][J]}

表示选择（不超过 ${C_{I}}$ 样或不选）前 ${I}$ 个物品在占用不超过 ${J}$ 容量时的最大的价值。
思路一（从完全背包推演）：由于只有

{C_{I}}

个物品，所以需要考虑第

{I}

个物品选择

{K (\leq C_{I})}

（下文的

{K}

同理）个最合适。同样，

{Dp[I][J]}

的设定同上。

选 ${K}$ 件第 ${I}$ 件物品，则此时的 ${Dp[I][J]=Dp[I-1][J-K*W_{I}]+K*V_{I}}$ ，当然，不能超过背包容量 ${Cap}$ ；
不选，就是 ${Dp[I][J]}$ 。此时，状态转移方程就是： ${ Dp[I][J]=\max \begin{cases} Dp[I][J],\\ Dp[I-1][J-K*M_{I}]+K*V_{I} \end{cases} }$
当然，由于三重循环可能会爆 TLE，所以在实现时可以考虑每次比上次多选一件或不选，再取最大值。

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

需要优化：因为这样相当于二进制选择，而其会出现很多种重复的方案。所以考虑倍增（二次幂）优化：将一个物品拆成这样的序列： ${[1,2,...,C_{I}-2^{N}(C_{I} \geq 2^{N})]}$ ，然后将价值和重量套回去就可以了！
请注意：对于高次幂的物品倍增方法（如果 ${Byte \geq 10}$ ，那就会适得其反），因为每增加一个进制单位，就会冗余一个单件的物品（除非你刚刚好是某个进制的前几项的和），反而会效果变差。

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

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

这算一个线性 DP 的扩展版。

符号说明

{Dp}

= 动态规划状态数组；

{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]}

文章操作

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

1.1 LIS 最长上升子序列

1.2 LNDS 最长不降子序列

1.3 LNIS 最长不升子序列

1.4 LCS 最长公共子序列

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

2.1 01 背包

2.2 ON 背包（完全背包）

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

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

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

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

6. 记忆化 DFS（MemoizatIon DFS）

7. 记忆化 BFS（MemoizatIon BFS）

相关推荐

评论

一般 DP 转移方程