动态规划

动态规划算法问题

• 什么叫作最优子结构? 和动态规划有什么关系?
• 为什么动态规划遍历DP数组的方式有正着遍历,有倒着遍历,有斜着遍历?

最优子结构

• 最优子结构是某些问题的一种特定的性质,并不是动态规划问题所特有的.
• 很多问题都具有最优子结构,但是其中大部分不具有重叠子问题,所以不会归为动态规划系列的问题
• 最优子结构:
  • 可以从子问题的最优结果推导出更大规模问题的最优结果
  • 子问题之间必须相互独立
• 通过改造问题来优化由于子问题之间不独立而导致的最优子结构失效的情况:
  • 问题: 假设学校有10个班,已知每个班的最高分与最低分差值的最大分数差,需要计算全校学生中的最大分数差
  • 分析: 这样的问题就无法通过这10个班的最大分数差来推导出来,因为这10个班的最大分数差不一定就包含全校学生的最大分数差.比如全校的最大分数差可能是由8班的最高分和6班的最低分的分数差而得.这样就导致子问题之间不是互相独立的
  • 改造问题: 直接进行问题改造

  int result = 0;
  for (Student a : school) {
    for (Student b : school) {
        if (a is b) {
            continue;
        } 
        result = max(result, |a.score - b.score|)
    }
  }
  return result;
  

• 改造问题就是将问题等价转化:
  • 最大分数差就等价于最高分数与最低分数的差
  • 那么就是要求最高和最低分数
  • 求最高分数是具备最优子结构的,求最低分数也是具有最优子结构的
  • 这样就样一个不具备最优子结构的问题转化为具备最优子结构的子问题
  • 借助最优子结构解决最值问题,再解决最大分数差问题
• 题目: 求一棵二叉树的最大值,假设节点中的值都为非负数

int maxVal(TreeNode root) {
    if (root == null) {
        return -1;
    }
    int left = maxVal(root.left);
    int right = maxVal(root.right);
    return max(root.val, left, right);
}

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

最优子结构总结

• 最优子结构并不是动态规划独有的一种性质,但是能求最值的问题大部分都会具备最优子结构的性质
• 最优子结构性质作为动态规划问题的必要条件,一定是可以用来求最值的: 通常情况下,最值的问题,思路往动态规划想就对了
• 动态规划就是从最简单的base case往后推导, 类似一种链式反应.但是只有具备最优子结构的问题,才会有发生这种链式反应的性质
• 最优子结构的寻找过程:
  • 就是证明状态转移方程正确性的过程
  • 方程符合最优子结构就可以直接递归求解
  • 写出直接递归求解后可以根据递归树看出有没有重叠子问题,如果有则进行优化

DP数组的遍历方向

• 动态规划中DP数组遍历顺序问题:
  • 示例: 二维DP数组
    • 正向遍历:

    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            /*
             * 计算dp[i][j]
             */  
             ...
        }   
    }   
    

    • 反向遍历:

    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]
             */
             ...
        }
    }
    

    • 斜向遍历:

    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 - 1;
            /*
             * 计算dp[i][j]
             */
        }
    }
    

• DP数组的遍历的两条原则:
  • 遍历的过程中,所需的状态必须是已经计算出来的
  • 遍历的终点必须是存储结果的位置

编辑距离问题

• 通过对DP数组的定义,确定了:
  • base case : dp[n][0] 和dp[0][n]
  • 最终答案 : dp[m][n]
• 通过状态转移方程知道:
  • dp[i][j] 需要从dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 转移而来
• 再根据DP数组遍历的两条原则,确定使用正向遍历:

for (int i = 1; i < m; i++) {
    for (int j = 1; j < n; j++) {
        /*
         * 通过dp[i-1][j], dp[i][j-1], dp[i-1][j-1]计算dp[i][j]
         */
    }
}

• 这样每一步迭代的左边,上边,左上边的位置都是base case或者之前计算出来的值
• 最终结束在结果的位置dp[m][n]

回文子序列

• 通过对DP数组的定义,确定了:
  • base case处在中间的对角线
  • 最终答案: dp[0][n-1]
• 通过状态转移方程知道:
  • dp[i][j] 需要从dp[i+1][j], dp[i][j-1], dp[i+1][j-1] 转移而来
• 再根据DP数组遍历的两条原则,确定有两种遍历方式:
  • 从左至右斜着遍历
  • 从下向上从左到右遍历
• 这样每一步迭代的左边,下边,左下边已经计算出来值
• 最终结束在结果的位置 dp[0][n-1]

DP数组遍历总结

• DP数组遍历主要就是看base case和最终结果的存储位置类决定遍历顺序
• 选择的遍历顺序要保证遍历过程中使用的数据都是计算完毕的