动态规划的最优子结构原理和dp数组遍历方向(我的学习笔记)_动态规划的最优子集

本文主要思考问题

• 到底什么才叫 最优子结构，和动态规划有什么关系。
• 如何判断一个问题是动态规划问题，即如何看出是否存在重叠子问题。
• 为什么经常看到将dp数组的大小设置为n+1,而不是n。
• 为什么动态规划遍历dp数组的方式五花八门，有的正着遍历，有的倒着遍历，有的斜着遍历。

一. 最优子结构详解

最优子结构并不是动态规划独有的一种性质，能求最值的问题大部分都具有这个性质；但反过来，最优子结构性质作为动态规划的必要条件，一定是让你求最值的。

动态规划就是从简单的base case往后推导，可以想象成一个链式反应，以小博大。但只有符合最优子结构的问题，才有发生这种链式反应的性质。

找最优子结构的过程，其实就是证明状态转移方程正确性的过程。方程符合最优子结构就可以写暴力解，写出暴力解就可以看出有没有重叠子问题，有则优化，无则OK。

想满足最优子结构，子问题之间必须相互独立。

最优子结构失效时，策略是：改造问题。

二. 如何一眼看出重叠子问题

正则表达式暴力解解法

bool dp(string& s, int i, string& p, int j) {
    int m = s.size(), n = p.size();
    if (j == n)  return i == m;
    if (i == m) {
        if ((n - j) % 2 == 1) return false;
        for (; j + 1 < n; j += 2) {
            if (p[j + 1] != '*') return false;
        }
        return true;
    }
 
    if (s[i] == p[j] || p[j] == '.') {
        if (j < n - 1 && p[j + 1] == '*') {
            return dp(s, i, p, j + 2)
               || dp(s, i + 1, p, j);
        } else {
            return dp(s, i + 1, p, j + 1);
        }
    } else if (j < n - 1 && p[j + 1] == '*') {
        return dp(s, i, p, j + 2);
    }
    return false;
}
 

代码十分复杂，我们不画图，直接忽略所有细节代码和条件分支，只抽象出递归框架：

bool dp(string& s, int i, string& p, int j) {
    dp(s, i, p, j + 2);     //#1
    dp(s, i + 1, p, j);     //#2
    dp(s, i + 1, p, j + 1); //#3
}

这个解的状态也是(i, j)的值，那么如何解决这个问题：状态(i, j) 转移到状态(i + 2, j + 2)，有几条路径？

显然，至少有两条路径：(i, j) -> #1 -> #2 -> #2 和 (i, j) -> #3 -> #3 ,这就说明解法存在巨量子问题。

三. dp数组的大小设置

编辑距离问题的自顶向下递归解法

int minDistance(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    // 按照 dp 函数的定义，计算 s1 和 s2 的最小编辑距离
    return dp(s1, m - 1, s2, n - 1);
}
 
// 定义：s1[0..i] 和 s2[0..j] 的最小编辑距离是 dp(s1, i, s2, j)
int dp(String s1, int i, String s2, int j) {
    // 处理 base case
    if (i == -1) {
        return j + 1;
    }
    if (j == -1) {
        return i + 1;
    }
 
    // 进行状态转移
    if (s1.charAt(i) == s2.charAt(j)) {
        return dp(s1, i - 1, s2, j - 1);
    } else {
        return min(
            dp(s1, i, s2, j - 1) + 1,
            dp(s1, i - 1, s2, j) + 1,
            dp(s1, i - 1, s2, j - 1) + 1
        );
    }
}
 

编辑距离问题的自底而上迭代算法

int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    //dp[i][j] 表示word1[0...i]与word2[0...j]的编辑距离
    int[][] dp = new int[m + 1][n + 1];
 
    //base case: 两个空字符串之间编辑距离为零，空字符串与非空字符串之间的编辑距离为
    //           非空字符串的长度(一直向空字符串中添加非空字符串的每个字符即可变为此非空字符串)
    dp[0][0] = 0;
    for (int i = 1; i <= m; i++) {
        dp[i][0] = i;
    }
    for (int j = 1; j <= n; j++) {
        dp[0][j] = j;
    }
 
    //进行状态转移
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                        dp[i - 1][j] + 1, //word2尾部插入
                        Math.min(dp[i][j - 1] + 1, //wordq1尾部插入
                                dp[i - 1][j - 1] + 1) //word1或word2尾部替换
                );
            }
        }
    }
 
    //得出结果
    return dp[m][n];
}

这两种解法思路是完全相同的，但就有读者提问，为什么迭代解法中的 dp 数组初始化大小要设置为 int[m+1][n+1]？为什么 s1[0..i] 和 s2[0..j] 的最小编辑距离要存储在 dp[i+1][j+1] 中，有一位索引偏移？

能不能模仿 dp 函数的定义，把 dp 数组初始化为 int[m][n]，然后让 s1[0..i] 和 s2[0..j] 的最小编辑距离要存储在 dp[i][j] 中？

理论上，你怎么定义都可以，只要根据定义处理好 base case 就可以。

在利用dp函数的递归解法中，dp(String s1, int i, String s2, int j) 代表着 s1[0..i] 和 s2[0..j] 的最小编辑距离，且在函数dp中对base case进行了处理， i, j 等于 -1时代表空串的 base case。

在利用dp[][]数组的迭代解法中，dp[0][0]表示空串时的base case。所以我们把 dp 数组初始化为 int[m+1][n+1]，让索引整体偏移一位，把索引 0 留出来作为 base case 表示空串，然后定义 dp[i+1][j+1] 存储 s1[0..i] 和 s2[0..j] 的编辑距离。

四. 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;i>=0;i--){
      for(int j = n;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++){
          j = l + i - 1;
          //计算dp[i][j]
      }
  }
  

• 有时正反遍历都能得到结果，比如我们在团灭股票问题中有的地方就正反皆可。

  [!IMPORTANT]

  如何选择dp数组遍历方向，主要把握两点：

  1. 遍历的过程中，所需的状态必须是已经计算出来的
  2. 遍历结束后，存储结果的那个位置必须已经被计算出来

  详见labuladong算法笔记

反向遍历：LeetCode115 不同的子序列

int numDistinct(String s, String t) {
    int m = s.length();
    int n = t.length();
 
    //dp[i][j] 表示s[i...m-1]中t[j...n-1]出现的个数
    int[][] dp = new int[m + 1][n + 1];
    //base case:
    //1.空序列是任何序列的子集
    for (int i = 0; i <= m; i++) {
        dp[i][n] = 1;
    }
    //若s[i]为空，且t不为空，则s中t的个数为0
    for (int j = 0; j < n; j++) {
        dp[m][j] = 0;
    }
 
    //状态转移
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            if (s.charAt(i) == t.charAt(j)) {
                //首字符相等，则有加入匹配和不加入匹配两种情况
                dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
            } else {
                dp[i][j] = dp[i+1][j];
            }
        }
    }
    return dp[0][0];
}

正向遍历，从上到下，从左往右 LeetCode1227 统计全为1的正方形子矩阵

//dp[i][j]表示以(i,j)为右下角的正方形的最大边长
int countSquares(int[][] matrix) {
    int row = matrix.length;
    int column = matrix[0].length;
 
    int[][] dp = new int[row][column];
    int ans = 0; //跟随（i,j）走动，记录所有正方形子矩阵的个数
    //base case:从左上到右下进行迭代，第一行和第一行无需迭代，直接为base case
    for (int j = 0; j < column; j++) {
        dp[0][j] = matrix[0][j];
        ans += dp[0][j];
    }
    for (int i = 1; i < row; i++) {
        dp[i][0] = matrix[i][0];
        ans += dp[i][0];
    }
 
    //状态转移：dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < column; j++) {
            if (matrix[i][j] == 1)
                dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
            else dp[i][j] = 0;
            ans += dp[i][j];
        }
    }
 
    return ans;
}

从状态转移：dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])中我们可以看出，要想求解dp[i][j],必须要先知道正左方dp[i][j-1],左上角dp[i-1][j-1]以及正上方dp[i][j-1]的值。

所以我们采用正向遍历，从第一行开始，从左往右遍历每一列，然后第二行、第三行、... 、最后一行。

[!NOTE]

在不能立刻找出状态方程时，先枚举几个例子。比如这个统计正方形子矩阵的题，先拿一个四维矩阵作例子，从[0][0]开始遍历，多遍历几个，你就发现在遍历每个单点（i，j）时，把以其为右下角元素的最大正方形边长加上，就是现在遍历到这个位置时的子矩阵个数。

LeetCode343 整数拆分 第一次与数论结合

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。返回可以取得的最大值。

[!TIP]

解决此题需要以下两个推论：

1. 一个数被拆分成k个数的和，当这k个数相等时，这些整数的乘积最大。 （算术均值不等式）
2. 假设拆分因子为整数x，要想使拆分后的所有整数数乘积最大，x越接近3越好。（详见LeetCode题解）其实就是求导证明。

int integerBreak(int n) {
    if (n <= 3) {
        return 1 * (n - 1);
    }
 
    //因数尽量取3，次之取2，如果余数是1，则取一个3和1构成2*2
    int num = (int) (n % 3); //记录余数
    if (num == 0) {
        return (int) Math.pow(3, n / 3);
    } else if (num == 2) {
        return (int) (Math.pow(3, n / 3)) * 2;
    } else {
        return (int) (Math.pow(3, n / 3 - 1)) * 4;
    }
}

动态规划解决此题：

对于正整数 n，当 n≥2 时，可以拆分成至少两个正整数的和。令 x 是拆分出的第一个正整数，则剩下的部分是 n−x，n−x 可以不继续拆分，或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。

创建数组 ，其中 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积。特别地，0 不是正整数，1 是最小的正整数，0 和 1 都不能拆分，因此 。

当 i≥2 时，假设对正整数 i 拆分出的第一个正整数是 （），则有以下两种方案：

• 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j×(i−j)；
• 将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 。

  因此，当 j 固定时，有 。由于 j 的取值范围是 1 到 i−1，需要遍历所有的 j 得到 的最大值，因此可以得到状态转移方程如下：

  最终得到 的值即为将正整数 n 拆分成至少两个正整数的和之后，这些正整数的最大乘积

  int integerBreak(int n) {
      if (n <= 3) return 1 * (n - 1);
      //利用动态规划  将n拆分为x 与 n-x,n的最大乘积为x的最大乘积乘以n-x的最大乘积
      // dp[n] = dp[x]*dp[n-x]
   
      int[] dp = new int[n + 1];
      //base case
      Arrays.fill(dp, -1);
      dp[1] = 1;
      dp[2] = 2;
   
      //状态转移
      for (int i = 3; i <= n; i++) {
          for (int j = 1; j <= i / 2; j++) {
              dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
          }
      }
   
      return dp[n];
  }