516. 最长回文子序列

给你一个字符串 s ,找出其中最长的回文子序列,并返回该序列的长度。

子序列定义为:不改变剩余字符顺序的情况下,删除某些字符或者不删除任何字符形成的一个序列。

示例 1:

输入:s = “bbbab”
输出:4
解释:一个可能的最长回文子序列为 “bbbb” 。

示例 2:

输入:s = “cbbd”
输出:2
解释:一个可能的最长回文子序列为 “bb” 。

提示:

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成

算法思路:

考虑 动态规划dp[i][j] 表示 字符串 s 在 [i, j] 范围内最长回文子序列的长度。递推公式如下:

  • 如果 s[i]与 s[j] 相同,则回文子序列长度为其中间的 +2,即 dp[i][j] = dp[i + 1][j - 1] + 2;
  • 不相同则说明 s[i] 和 s[j] 的同时加入并不能增加 [i,j] 区间回文子序列的长度,那么分别加入 s[i]、s[j] 看看哪⼀个可以组成最长的回文子序列,即 dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);

代码实现:

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        //⼀个字符的回⽂⼦序列⻓度就是 1
        for (int i = 0; i < n; i++) dp[i][i] = 1;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                // s[i]与 s[j]相同,则回⽂⼦序列⻓度为其中间的 +2
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    //如果 s[i]与 s[j]不相同,说明s[i]和s[j]的同时加⼊并不能增加 [i,j] 区间回⽂⼦序列的⻓度,
                    // 那么分别加⼊s[i]、s[j]看看哪⼀个可以组成最⻓的回⽂⼦序列
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
}

Q.E.D.


以无限为有限,以无法为有法