No.516 最长回文子序列

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

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

示例 1：

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

示例 2：

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

提示：

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

思路分析

其实有一个非常关键的思路。就是
字符串s的最长回文子序列 等价于 字符串s和s的倒序s'的最长公共子序列

简单的证明，s与s倒序的最长公共子序列一定是回文的。正着有，反着有，且相同，这就是回文的定义。
也不会有比s与s倒序的最长公共子序列更长的回文子序列了。如果有，那么s与s倒序的最长公共子序列也会变得更长。

所以我们成功的将题目转化为求s与s倒序的最长公共子序列的长度。

既然是这样，就非常方便了。直接使用二维动态规划即可轻松求解。 首先设置动态规划变量dp[n+1][n+1](预留一个空位方便计算)。

再说dp[i][j]的含义，就是s中前i位与s'中前j位的最长公共子序列。

动态规划的递推式也非常好思考。只要遇到了两个相同的字符，dp[i][j] = dp[i - 1][j - 1] + 1
否则，dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

Rust代码

#![allow(unused)]
fn main() {
struct Solution;
impl Solution {
    pub fn longest_palindrome_subseq(s: String) -> i32 {
        let s = s.into_bytes();
        let n = s.len();
        let mut res = 0;
        let mut dp = vec![vec![0; n + 1]; n + 1];
        for i in 1..=n {
            for j in 1..=n {
                if s[n - i] == s[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
                }
            }
        }

        dp[n][n]
    }
}
}