序列类动态规划

序列类动态规划是指对给定的两个或多个序列（如字符串、数组）进行计算，常见的题目包括：最长公共子序列（LCS）、最长递增子序列（LIS）、编辑距离等。

核心思想

这类问题的状态通常定义为两个序列的前缀状态。

最长公共子序列 LCS

给定两个字符串 text1 和 text2，找出其最长公共子序列的长度。

状态转移方程

• 如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
• 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.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];
}

最长递增子序列 LIS

给定一个数组 nums，找到其中最长严格递增子序列的长度。

动态规划版本 (O(n²))

• dp[i] 表示以 i 结尾的最长递增子序列长度。
• dp[i] = max(dp[j] + 1)，其中 j < i 且 nums[j] < nums[i]。

二分查找优化 (O(n log n))

使用 tails[i] 存储长度为 i+1 的最小结尾元素。

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] tails = new int[n];
    int size = 0;
    for (int num : nums) {
        int left = 0, right = size;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] < num) left = mid + 1;
            else right = mid;
        }
        tails[left] = num;
        if (left == size) size++;
    }
    return size;
}

编辑距离 Edit Distance (LeetCode 72)

计算将字符串 word1 转换为 word2 的最小操作次数（插入、删除、替换）。

状态定义

dp[i][j] 表示将 word1[0...i-1] 转换为 word2[0...j-1] 的编辑距离。

状态转移

• 如果 word1[i-1] == word2[j-1]，则 dp[i][j] = dp[i-1][j-1]
• 否则 dp[i][j] = 1 + min(插入(dp[i][j-1]), 删除(dp[i-1][j]), 替换(dp[i-1][j-1]))

二维矩阵路径问题

1. 不同路径 (Unique Paths)

每次只能向下或向右。 dp[i][j] = dp[i-1][j] + dp[i][j-1]

2. 最小路径和 (Min Path Sum)

每次只能向下或向右，求路径上数字之和最小值。 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

练习

1. LeetCode 1143：最长公共子序列
2. LeetCode 300：最长递增子序列
3. LeetCode 72：编辑距离
4. LeetCode 62/63：不同路径 I/II (含障碍)
5. LeetCode 64：最小路径和
6. LeetCode 5：最长回文子串
7. LeetCode 516：最长回文子序列