动态规划之最长回文子序列

516. 最长回文子序列

1312. 让字符串成为回文串的最少插入次数

先介绍几个概念：子序列，子串，子数组

• 「子序列」和「子串」是针对字符串的，它们俩唯一的区别在于「子串」在原字符串中必须是连续的，而「子序列」可以是零散的
• 「子数组」是针对数组的，它和「子串」的概念很相似，只不过对象不同：字符串 or 数组

再推荐一些相应的文章，有兴趣的可以点击下方链接 🔗

• 动态规划设计：最长递增子序列
• 最长公共子序列 (LCS)：「模版」&「输出」
• 关于回文子串的两种方法：「中心扩展」&「动态规划」
• 最长重复子数组

上面提到了一篇「回文」和「子串」相结合的动态规划问题；下面进入本篇文章的重点：「回文」和「子序列」相结合的动态规划问题！！

本篇文章整理了两个题目，准备先用「记忆化搜索 (回溯 + 备忘录)」，然后再用「二维 dp」，最后优化成「一维 dp」

之前已经总结过一道题目既用「回溯」又用「动规」去解决，有兴趣的可以点击下方链接 🔗

• 目标和 -「回溯」&「动规」
• 下降路径最小和 -「回溯」&「动规」

最长回文子序列

题目详情可见 最长回文子序列

记忆化搜索

既然要「记忆化搜索」，首先定义一波emeo[i][j]的含义：表示字符串s在区间[i...j]中的最长回文子序列的长度

搜索方向：从两边开始搜，向中间收拢，如下图所示：

这里有两种情况：

• 当s[i] = s[j]时，向[i + 1, j - 1]搜索 🔍
• 当s[i] != s[j]时，向[i, j - 1]和[i + 1, j]搜索，取最大值

下面给出代码，配合注释食用更佳哦！！

xxxxxxxxxx
private int n;
private String s;
private int[][] emeo; // 备忘录数组
public int longestPalindromeSubseq(String s) {
    this.s = s;
    n = s.length();
    emeo = new int[n][n];
    // 直接从 [0...n-1] 开始搜，向中间收拢
    return dfs(0, n - 1);
}
private int dfs(int i, int j) {
    // 区间非法，返回 0
    if (i > j) return 0;
    // 区间长度为 1，肯定是长度为 1 的回文
    if (i == j) return 1;
    // 判断 [i...j] 是否已经被计算过
    if (emeo[i][j] != 0) return emeo[i][j];
    // 两边的字符相等
    if (s.charAt(i) == s.charAt(j)) emeo[i][j] = dfs(i + 1, j - 1) + 2;
    // 两边的字符不相等
    else emeo[i][j] = Math.max(dfs(i + 1, j),dfs(i, j - 1));
    return emeo[i][j];
}

二维 dp

上述「记忆化搜索」可以很容易的转化成「二维 dp」的方式，即从「递归」到「递推」

dp[][]数组的定义：dp[i][j]表示s[i...j]的最长回文子序列的长度

状态转移方程：

base case 也很简单，所有长度为 1 的子序列的值都为 1，更具体的可以看下图：

到目前为止所介绍的内容都很常规，在开头推荐的动态规划文章中都有反复总结。之所以单独拿出来总结是因为这里要提到一个新的知识点「遍历顺序」

按照常规的二维动态规划问题，遍历顺序为：

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

按照这种「遍历顺序」，当我们求dp[i][j]时，dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]肯定都已经被求出来了

但是但是但是这个题目却有亿点点不一样了！！

如果我们还是按照上述的「遍历顺序」，当我们求dp[i][j]时，dp[i + 1][j - 1], dp[i + 1][j]根本就没有求出来，所以必然会出现问题

有没有发现上面两个图是「上下对称」的结构，所以我们可以从下往上遍历，如下图所示：

其中，虚线表示不需要处理的部分，原因：虚线部分均满足：i > j，属于无效区间

下面给出代码：

xxxxxxxxxx
public int longestPalindromeSubseq(String s) {
    int ans = 1;
    int n = s.length();
    int[][] dp = new int[n][n];
    // base case
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    // 从 n - 1 行开始向上 👆
    for (int i = n - 1; i >= 0; i--) {
        // 由于只需要遍历右上部分，j 从 i + 1 开始即可
        for (int j = i + 1; j < n; j++) {
            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];
}

一维 dp

有读者可能感觉到上面就结束了，但是这里再来一波空间上的优化，从 $n^2$$n^2$ 直接到 $n$$n$，这也是几百年前埋下的一个坑 目标和-回溯-动规：动态规划优化

根据「遍历顺序」可以看出，当我们求第i行结果的时候，只和第i + 1行有关系，所以完全可以把二维数组投影成一维

当我们在求第i行中dp[j]的值时：

• 此时dp[j]存的还是下一行的值，即等价于[i + 1][j]
• 此时dp[j - 1]存的是当前行前一个处理得到的值，即等价于[i][j - 1]

现在就出现了一个问题原二维数组中dp[i + 1][j - 1]会被dp[j - 1]覆盖

这个好办，我们定义一个变量在dp[j - 1]要被覆盖之前记录下原来的值

下面给出代码：

xxxxxxxxxx
public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = n - 1; i >= 0; i--) {
        int prev = 0;
        for (int j = i + 1; j < n; j++) {
            // 记录覆盖前的值
            int temp = dp[j];
            // if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;
            if (s.charAt(i) == s.charAt(j)) dp[j] = prev + 2;
            // else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            else dp[j] = Math.max(dp[j], dp[j - 1]);
            prev = temp;
        }
    }
    return dp[n - 1];
}

让字符串成为回文串的最少插入次数

题目详情可见 让字符串成为回文串的最少插入次数

本题和上个题目神似，也和「编辑距离」很像，详情可见 经典动态规划：编辑距离

记忆化搜索

同样的，既然要「记忆化搜索」，首先定义一波emeo[i][j]的含义：表示字符串s在区间[i...j]中让字符串成为回文串的最少插入次数

搜索方向：从两边开始搜，向中间收拢，如下图所示：

这里有两种情况：

• 当s[i] = s[j]时，向[i + 1, j - 1]搜索 🔍
• 当s[i] != s[j]时，向[i, j - 1]「表示删除 j 处的字符」和[i + 1, j]「表示删除 i 处的字符」搜索，取最小值

下面给出代码：

xxxxxxxxxx
private int n;
private String s;
private int[][] emeo;
public int minInsertions(String s) {
    n = s.length();
    if (n == 1) return 0;
    this.s = s;
    emeo = new int[n][n];
    // 根据 1 <= s.length <= 500 设置的一个上界
    for (int i = 0; i < n; i++) Arrays.fill(emeo[i], 666);
    // 直接从 [0...n-1] 开始搜，向中间收拢
    return dfs(0, n - 1);
}
private int dfs(int i, int j) {
    if (i >= j) return 0;
    if (emeo[i][j] != 666) return emeo[i][j];
    if (s.charAt(i) == s.charAt(j)) emeo[i][j] = dfs(i + 1, j - 1);
    else emeo[i][j] = Math.min(dfs(i + 1, j), dfs(i, j - 1)) + 1;
    return emeo[i][j];
}

二维 dp

和上一题神似，直接给出代码：

xxxxxxxxxx
public int minInsertions(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i + 1; j < n; j++) {
            if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1];
            else dp[i][j] = Math.min(dp[i + 1][j], dp[i][j - 1]) + 1;
        }
    }
    return dp[0][n - 1];
}

一维 dp

空间优化过程和上一题神似，直接给出代码：

public int minInsertions(String s) {
    int n = s.length();
    int[] dp = new int[n];
    for (int i = n - 1; i >= 0; i--) {
        int prev = 0;
        for (int j = i + 1; j < n; j++) {
            int temp = dp[j];
            if (s.charAt(i) == s.charAt(j)) dp[j] = prev;
            else dp[j] = Math.min(dp[j], dp[j - 1]) + 1;
            prev = temp;
        }
    }
    return dp[n - 1];
}