L-R范围上的尝试模型

核心思想

• L和R的作用：L表示子问题的左端，R表示子问题的右端。在逐步扩展问题的过程中，我们从 L 和 R 的取值范围开始，逐渐填充并计算出最终的解。
• 填表的固定方式：填表的方式非常固定，通常在 主对角线 和 副对角线 上做一些特殊处理。
• 状态转移的方式：一般是通过倒推填表，确保前一个状态的结果能够依赖到当前状态。

动态规划填表的核心步骤

1. 初始化：首先初始化表格的边界，通常是单一元素的情况（例如区间的长度为1时），或者可以从主对角线和副对角线开始填充。
2. 递推过程：递推时会根据子问题的结果逐步填充表格，逐步扩大L和R的范围。
3. 最终结果：填表过程完成后，表格中的某些位置（通常是右上角或左下角）会包含最优解。

L-R范围模型的优势

1. 适用范围广：特别适用于那些问题中需要对区间进行逐步选择和计算的情境。
2. 空间和时间优化：通过填表优化递归过程，避免了大量的重复计算。很多问题的时间复杂度可以从指数级降低到多项式级。
3. 简洁的状态转移：状态转移公式通常非常直观，可以通过递推得到每个子问题的解。

常见问题类型

这种模型适用于一些具有“区间”性质的问题，比如：

• 矩阵链乘法：计算一系列矩阵的最优乘法顺序。
• 最短路径问题：在一个带权图中寻找从源节点到所有其他节点的最短路径。
• 最长公共子序列：在两个字符串中找出最长的公共子序列。
• 区间DP问题：如打折购物、分割问题等。

模型解析：矩阵链乘法问题

矩阵链乘法问题的目标是给定一系列矩阵，计算出最优的矩阵乘法顺序，使得计算所需的标量乘法次数最少。

1. 状态定义：定义一个二维数组 dp[i][j]，表示从矩阵 i 到矩阵 j 的最小乘法次数。

2. 状态转移：为了填充 dp[i][j]，我们需要选择一个切分点 k，将矩阵链 [i, j] 分成两部分：[i, k] 和 [k+1, j]。然后，dp[i][j] 就是从 i 到 k 和从 k+1 到 j 的最小乘法次数之和，再加上计算这两部分结果的乘法次数。

   假设矩阵 A[i] 的维度为 p[i-1] x p[i]，那么计算矩阵链 [i, j] 的乘法次数就是：

   $$dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+p[i]\ast p[k+1]\ast p[j]);$$

   其中，p[i-1] 是矩阵 A[i] 的行数，p[k] 是矩阵 A[k+1] 的行数，p[j] 是矩阵 A[j] 的列数。

3. 填表顺序：一般从较小的子问题（区间长度为1的子问题）开始逐步向大问题推导。

public static int matrixChainOrder(int[] p) {
    int n = p.length;
    int[][] dp = new int[n][n];

    for (int len = 2; len < n; len++) {
        for (int i = 0; i < n - len; i++) {
            int j = i + len;
            dp[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j]);
            }
        }
    }

    return dp[0][n-1];
}

模型解析：最长公共子序列问题

假设我们有两个字符串 X 和 Y，目标是找出它们的最长公共子序列。

力扣 1143. 最长公共子序列

1. 状态定义：定义 dp[i][j] 为字符串 X[0..i-1] 和 Y[0..j-1] 的最长公共子序列的长度。

2. 状态转移：如果 X[i-1] == Y[j-1]，则：

   $$dp[i][j]=dp[i-1][j-1]+1$$

   否则：

   $$dp[i][j]=max(dp[i-1][j],dp[i][j-1])$$

3. 填表顺序：逐步填充整个表格，从 (0,0) 到 (m,n)，最终 dp[m][n] 为结果。

public static int longestCommonSubsequence(String X, String Y) {
    int m = X.length();
    int n = Y.length();
    int[][] dp = new int[m+1][n+1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X.charAt(i-1) == Y.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }

    return dp[m][n];
}

复杂度分析

• 时间复杂度：O(N^2)，其中N为字符串或矩阵的长度。
• 空间复杂度：O(N^2)，由于我们需要一个二维数组存储状态。

总结

L-R范围上的尝试模型适合于解决区间类问题，核心思想是通过逐步构建子问题的解，从而得到最终的最优解。常见的应用包括矩阵链乘法、最长公共子序列等问题。填表顺序的固定性以及利用子问题解来递推求解，使得这个模型在很多问题中都非常有效。