1
2
3

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

1
2
3

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 动态规划
    /// 1. 设 dp[i][j]: 为s[i..j]的最长回文子序列;
    /// 2. 递推关系:
    ///                   = dp[i-1][j-1] + 2 (s[i] == s[j])
    ///    如果: dp[i][j] or
    ///                   = max(dp[i+1][j-1], dp[i][j-1]) (s[i] != s[j])
    /// 3. 初始条件: dp[i][i] = 0
    /// 4. 目标: dp[0][n-1]
    pub fn longest_palindrome_subseq(s: String) -> i32 {
        let mut res = 1;
        let sb = s.as_bytes();
        let mut dp = vec![vec![0; sb.len()]; sb.len()];
        for i in (0..s.len() - 1).rev() {
            dp[i][i] = 1;
            for j in (i + 1)..s.len() {
                dp[i][j] = if sb[i] == sb[j] {
                    dp[i + 1][j - 1] + 2
                } else {
                    dp[i + 1][j].max(dp[i][j - 1])
                };
                res = res.max(dp[i][j]);
            }
        }

        res
    }
}
// @lc code=end

struct Solution;