动态规划三:常见递推关系式
- 常见状态
- 坐标型
- 前缀划分型
- 前缀匹配型
- 区间型
- 背包型
常见状态
坐标型
-
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)所得到的图的一个拓扑排序)。
如果子问题的数目为 ,且每个子问题需要依赖于 个其他子问题,则称这个问题为
总结起来可得到四种典型的动态规划关系递推方程:、、、。
定义一个实函数 ,已知 ,状态转移方程:
P.S. opt 是最优关系,可能是 max,也可能是 min。
其中, 可以根据
《算法导论》里的切分钢条,锯木头问题,最长上升子序列都是这种结构。
已知 和 ,状态转移方程为:
其中,
线性DP(如最长公共子序列)、串DP 问题,多是这种结构,具体的理解,您要在行动中来思考。
定义实函数 ,已知 ,状态转移方程为:
区间动态规划模型多是这种结构。
区间动态规划,顾名思义,就是求解一个区间内的某种最优解,这种题目在分解子问题的时候,通常考虑子问题就是其中任意一个子区间,而规划的内容就是如何分解子区间。无论题目内容怎样,算法的实现模式基本上就是一个如下所示的三重循环。
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 分别与 比较,根据题目的要求,用最优值更新
当全部三重循环都完成后,题目要求的解就在
这就是区间动态规划的解题思路和实现模板,具体的理解,您要在行动中来思考。
定义实函数 ,已知 和 ,状态转移方程为:
其中, 可以根据
对于以上四种典型方程,如果方程是 类型,可以套用上述递推关系式得到一个时间复杂度为 、空间复杂度