动态规划三：常见状态与常见递推关系式
动态规划三：常见递推关系式
常见状态坐标型前缀划分型前缀匹配型区间型背包型
常见递推关系式
1
D
1
D
\frac{1D}{1D}
1D1D
2
D
0
D
\frac{2D}{0D}
0D2D
2
D
1
D
\frac{2D}{1D}
1D2D
2
D
2
D
\frac{2D}{2D}
2D2D
常见状态
坐标型
dp[i]：从起点到坐标 i 的最值/方案数/可行性dp[i][j]：从起点到坐标 i, j 的最值/方案数/可行性
前缀划分型
dp[i]：前 i 个字符的最值/方案数/可行性dp[i][j]：前 i 个字符划分为 j 个部分的最值/方案数/可行性
前缀匹配型
dp[i][j]：第一个字符串的前 i 个字符匹配上第二个字符串的前 j 个字符的最值/方案数/可行性
区间型
dp[i][j]：区间 i-j 的最值/方案数/可行性
背包型
dp[i][j]：前 i 个物品里选出一些物品组成和为 j 的大小的最值/方案数/可行性
常见递推关系式
动态规划虽然飘逸，但还是有规律可循，前人还是总结了好几种常见的递推关系模式。
动态规划算法有三个要素：
所有不同的子问题所组成的表（它包含的问题数目称为问题的大小，即 size）；问题解决的依赖关系可以看成是一个图；填充子问题的顺序（实际上就是（2）所得到的图的一个拓扑排序）。
如果子问题的数目为
θ
(
n
t
)
\theta(n^{t})
θ(nt)，且每个子问题需要依赖于
θ
(
n
e
)
\theta(n^{e})
θ(ne) 个其他子问题，则称这个问题为
t
D
e
D
\frac{tD}{eD}
eDtD 问题。
总结起来可得到四种典型的动态规划关系递推方程：
1
D
1
D
\frac{1D}{1D}
1D1D、
2
D
0
D
\frac{2D}{0D}
0D2D、
2
D
1
D
\frac{2D}{1D}
1D2D、
2
D
2
D
\frac{2D}{2D}
2D2D。
1
D
1
D
\frac{1D}{1D}
1D1D
定义一个实函数
w
(
i
,
j
)
(
1
≤
i
<
j
≤
n
)
w(i,j)(1\leq i< j\leq n)
w(i,j)(1≤i D [ 0 ] D[0] D[0]，状态转移方程： E [ j ] = o p t 0 ≤ i < j { D [ i ] + w ( i , j ) } , i ≤ j ≤ n E[j]=\underset {0\leq i E[j]=0≤i P.S. opt 是最优关系，可能是 max，也可能是 min。 其中， D [ i ] D[i] D[i] 可以根据 E [ i ] E[i] E[i] 在常数时间内计算出来。 《算法导论》里的切分钢条，锯木头问题，最长上升子序列都是这种结构。 2 D 0 D \frac{2D}{0D} 0D2D 已知 D [ i , 0 ] D[i,0] D[i,0] 和 D [ 0 , j ] ( 0 ≤ i , j ≤ n ) D[0,j](0\leq i,j\leq n) D[0,j](0≤i,j≤n)，状态转移方程为： E [ i , j ] = o p t { D [ i − 1 , j ] + x i ， D [ i , j − 1 ] + y i , D [ i − 1 , j − 1 ] + z i j } E[i,j]=opt\{D[i-1,j]+x_{i}，D[i,j-1]+y_{i}, ~D[i-1,j-1]+z_{ij}\} E[i,j]=opt{D[i−1,j]+xi，D[i,j−1]+yi, D[i−1,j−1]+zij} 其中， x i , y i , z i x_{i},y_{i},z_{i} xi,yi,zi 都是可以在常数时间内算出来的。 线性DP（如最长公共子序列）、串DP 问题，多是这种结构，具体的理解，您要在行动中来思考。 2 D 1 D \frac{2D}{1D} 1D2D 定义实函数 w ( i , j ) ( 0 ≤ i < j ≤ n ) w(i,j)(0\leq i< j\leq n) w(i,j)(0≤i d [ i , j ] = 0 ( 1 ≤ i ≤ n ) d[i,j]=0(1\leq i \leq n) d[i,j]=0(1≤i≤n)，状态转移方程为： D [ i , j ] = w ( i , j ) + o p t i ≤ k ≤ j { D [ i , k − 1 ] + D [ k , j ] } ( 1 ≤ i < j ≤ n ) D[i,j]=w(i,j)+\underset {i\leq k \leq j}{opt}\{D[i,k-1]+D[k,j]\}(1\leq i< j \leq n) D[i,j]=w(i,j)+i≤k≤jopt{D[i,k−1]+D[k,j]}(1≤i 区间动态规划模型多是这种结构。 区间动态规划，顾名思义，就是求解一个区间内的某种最优解，这种题目在分解子问题的时候，通常考虑子问题就是其中任意一个子区间，而规划的内容就是如何分解子区间。无论题目内容怎样，算法的实现模式基本上就是一个如下所示的三重循环。 for(区间长度 size：从最小可分区间开始到最大区间长度) { for(小区间起始位置 i：从第一个位置开始到区间长度 size 所决定的结束位置) { j = i + szie - 1; // j 定义区间结束位置，具体计算方法因问题而异 for(区间分割点位置 k：从 i 开始到 j 结束) // 遍历所有区间 [i,j] 内的位置，将其分割为两个小区间 { f[i][j] = max(f[i][j],f[i][k]+f[k][j] + 某种最优值计算方法) 或 f[i][j] = min(f[i][j],f[i][k]+f[k][j] + 某种开销计算方法) } } } 第一重循环枚举区间的大小，一般是从最小可分解区间开始，直到最大区间长度。 为什么枚举区间长度要从“最小可分解区间”开始呢？ 因为区间长度太小的话，不满足题目的分解区间要求，后续的处理也没有意义。具体的“最小可分解区间”的值，因题而异，比如三角形组合问题，最小区间长度至少是 3 条边才行，否则连一个三角形都凑不齐，后续还怎么处理？对于经典的“石子合并”问题，区间长度就是石子的堆数，要能够合并，至少要 2 堆石子吧，所以石子堆数就从 2 开始枚举。 实现模式的第二重循环是对区间内的起始位置开始枚举。 第一重循环给定了区间的大小（范围）； 第二重循环就尝试从区间的不同位置开始定义子区间。 举个简单的例子，假设第一重循环给定了区间长度是 5，则第二重循环要处理的最大区间就是 [1,2,3,4,5]，第二重循环的作用就是分别尝试定义子区间，共可得到 5 个子区间： [1,2,3,4,5]、[2,3,4,5]、[3,4,5]、[4,5] 和 [5]； 第三重循环就是尝试对每个子区间分解，假设前两重循环选择了第二步分解的 5 个子区间中的第 2 个子区间，也就是 [2,3,4,5]，则 k 的值就是从 2 到 5，拆分子区间，共得到三组拆分结果：[2] 和 [3,4,5]、[2,3] 和 [4,5]、[2,3,4] 和 [5]。对于每一组拆分结果，计算状态值： state1 = f[2][2] + f[3][5] + 根据当前 k=2 的分解得到的某种最优值（或开销值） state2 = f[2][3] + f[4][5] + 根据当前 k=3 的分解得到的某种最优值（或开销值） state3 = f[2][4] + f[5][5] + 根据当前 k=4 的分解得到的某种最优值（或开销值） 而后将三个 state 分别与 f [ 2 ] [ 5 ] f[2][5] f[2][5] 比较，根据题目的要求，用最优值更新 f [ 2 ] [ 5 ] f[2][5] f[2][5] 的值。 当全部三重循环都完成后，题目要求的解就在 f [ 1 ] [ n ] f[1][n] f[1][n] 中。 这就是区间动态规划的解题思路和实现模板，具体的理解，您要在行动中来思考。 2 D 2 D \frac{2D}{2D} 2D2D 定义实函数 w ( i , j ) ( 0 ≤ i < j ≤ n ) w(i,j)(0\leq i w(i,j)(0≤i D [ i , 0 ] D[i,0] D[i,0] 和 D [ 0 , j ] ( 0 ≤ i , j ≤ n ) D[0,j](0\leq i, j \leq n) D[0,j](0≤i,j≤n)，状态转移方程为： E [ i , j ] = o p t 0 ≤ i ′ < i , 0 ≤ j ′ < j { D [ i ′ , j ′ ] + w ( i ′ + j ′ , i + j ) } 1 ≤ i , j ≤ n E[i,j]=\underset {0 \leq i' E[i,j]=0≤i′ 其中， D [ i , j ] D[i,j] D[i,j] 可以根据 E [ i , j ] E[i,j] E[i,j] 在常数时间内计算出来，具体的理解，您要在行动中来思考。 对于以上四种典型方程，如果方程是 t D e D \frac{tD}{eD} eDtD 类型，可以套用上述递推关系式得到一个时间复杂度为 θ ( n t + e ) \theta(n^{t+e}) θ(nt+e)、空间复杂度 θ ( n t ) \theta(n^{t}) θ(nt) 的算法。