序列 DP：编辑距离与字符串 DP

编辑距离（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]
• 否则，取三种操作中的最小：
  • 替换：改 word1[i-1]，dp[i][j] = dp[i-1][j-1] + 1
  • 删除：删 word1[i-1]，dp[i][j] = dp[i-1][j] + 1
  • 插入：在 word1[i] 后插入 word2[j-1]（等价于删除 word2[j-1]），dp[i][j] = dp[i][j-1] + 1

初始化

• dp[0][j] = j（word1 为空，需插入 j 个字符）
• dp[i][0] = i（word2 为空，需删除 i 个字符）

int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; 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] = 1 + Math.min(dp[i-1][j-1],     // 替换
                                Math.min(dp[i-1][j],        // 删除
                                         dp[i][j-1]));      // 插入
            }
        }
    }
    return dp[m][n];
}

最长公共子序列（LCS）

dp[i][j] = text1[0..i-1] 和 text2[0..j-1] 的 LCS 长度

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];
}

最长回文子序列

dp[i][j] = s[i..j] 中最长回文子序列的长度（区间 DP）

int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;   // 单字符
    for (int len = 2; len <= n; len++) {           // 枚举区间长度
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][n-1];
}

不同的子序列（LeetCode 115）

s 的子序列中，有多少种等于 t 的？

dp[i][j] = s[0..i-1] 的子序列中等于 t[0..j-1] 的数量

int numDistinct(String s, String t) {
    int m = s.length(), n = t.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = 1;  // 空子序列
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= Math.min(i, n); j++) {
            dp[i][j] = dp[i-1][j];  // 不用 s[i-1]
            if (s.charAt(i-1) == t.charAt(j-1))
                dp[i][j] += dp[i-1][j-1];  // 用 s[i-1] 匹配 t[j-1]
        }
    }
    return dp[m][n];
}

戳气球（区间 DP，LeetCode 312）

逆向思维：不考虑先戳哪个，而是考虑最后戳哪个（分治+记忆化）。

dp[i][j] = 将 balloons[i+1..j-1] 全部戳完后能得到的最多硬币（i 和 j 是边界哨兵，不戳）。

int maxCoins(int[] nums) {
    int n = nums.length;
    int[] arr = new int[n + 2];
    arr[0] = arr[n + 1] = 1;
    for (int i = 1; i <= n; i++) arr[i] = nums[i-1];
    int[][] dp = new int[n + 2][n + 2];
    // 枚举区间长度
    for (int len = 2; len <= n + 1; len++) {
        for (int left = 0; left <= n + 1 - len; left++) {
            int right = left + len;
            // 枚举最后一个戳的气球 k（在 left 和 right 之间）
            for (int k = left + 1; k < right; k++) {
                dp[left][right] = Math.max(dp[left][right],
                    dp[left][k] + arr[left] * arr[k] * arr[right] + dp[k][right]);
            }
        }
    }
    return dp[0][n + 1];
}

字符串 DP 总结