0%

dp技巧学习

最优子结构详解

最优子结构:从子问题的最优结果推出更大规模的问题的最优结果。

例如,假设学校有10个班级,已经每个班级的最高分,要求全校的最高分。

这个问题就符合最优子结构:可以从子问题的最优结果推出更大规模问题的最优结果。计算每个班的最高分就是子问题。

这么简单的问题都具有最优子结构,但是因为没有重叠子问题,因此不用动态规划来解决。

再例如,假设学校有10个班级,已经每个班级都最大分数差,求出全校学生的最大分差。这个问题可以想办法算,但是肯定不能根据已知的最大分差来进行推,因为10个班的最大分差就不一定是全校的最大分差,有可能是 3 班的最高分和 6 班的最低分之差。

那么这次的这个问题就不符合最优子结构。没办法根据每个班的最优值推出规模更大问题的最优值。因为要想满足最优子结构,那么子问题之间必须要相互独立。最大分差可能出现在两个班级,子问题并不独立,所以这个问题不符合。

遇到这种情况,我们就需要对问题进行一个改造。先写一段暴力代码:

1
2
3
4
5
6
7
8
9
10
int result = 0;
for (Student a: school) {
for (Student b: school) {
if (a is b) {
continue
} else {
result = max (result, abs(a - b))
}
}
}

把问题来一波等价转换:最大分数差等价于最高分数和最低分数的差,这样不就具备有最优子结构了吗?

再举一个常见的例子,求一颗二叉树的最大值(假设节点中都是非负数):

1
2
3
4
5
6
7
8
int maxVal (TreeNode root) {
if (!root){
return -1;
}
let left = maxVal(root.left);
let right = maxVal(root.right);
return max(root.val, left, right);
}

这个问题其实也符合最优子结构,以 root 为根的树的最大值,可以通过两边子树(子问题)的最大值推导出来。

但这也不是dp问题,最优子结构并不是dp独有的一种性质,能求最值的问题大部分都具备这个性质;但是反过来,最优子结构性质作为dp问题的必要条件,一定是用来求最值的。

找最优子结构的过程,其实就是证明状态转移方程正确性的过程,方程符合最优子结构就可以写暴力解了,写出暴力解就可以观察是否出现重复的子问题,有的话就优化。

dp数组遍历的方向

以二维dp作为例子,有时候是正向遍历:

1
2
3
4
5
6
int [][]dp = new int [m][n];
for (int i = 0;i<m;i++) {
for (int j = 0;j<n;j++) {
// 计算dp[i][j]
}
}

有时候反向:

1
2
3
4
5
6
int [][]dp = new int [m][n];
for (int i = m- 1;i>=0;i--) {
for (int j = n - 1;j>=0;j--) {
// 计算dp[i][j]
}
}

也可以斜着遍历:

1
2
3
4
5
6
7
int dp = new int [m][n];
for (int l = 2;l<=n;l++) {
for (int i = 0;i<=n-l;i++) {
int j = l + i - 2;
dp[i][j] = ...
}
}

其实如果仔细观察的话,只需要掌握以下两点即可:

  • 遍历过程中,所需要的状态已经被计算出来了
  • 遍历的终点必须是存储结果的那个位置

以编辑距离这个题目作为例子,对dp数组的定义,确定的base的数组值是dp[...][0]dp[o][...],最终的答案是dp[m][n];而且我们通过状态转移方程知道dp[i][j]需要从dp[i-1][j]dp[i][j-1]dp[i-1][j-1]转移而来,如下图:

image-20200525165037985

参考之前的原则,那么这里我们肯定会去正向遍历数组:

1
2
3
4
5
for (int i = 1;i<m;i++) {
for (let j = 1;j<n;j++) {
// 通过 dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1] -> dp[i][j]
}
}

再参考回文子序列问题,可以参考前面的”子序列问题模版”,通过对dp数组的定义,确定了base case处于中间的对角线,dp[i][j] 需要从dp[i+1][j]dp[i][j-1]dp[i+1][j-1]转移而来。

image-20200525165748819

根据刚才的两个原则,就可以有两种正确的遍历方式:

image-20200525165901880

要么从左到右斜着遍历,要么从下到上从左到右遍历,这样才能保证每次dp[i][j]到左边、下边、左下角已经计算完成,得到了正确的结果。