516. 最长回文子序列

 1 class Solution 
 2 {
 3 public:
 4     int longestPalindromeSubseq(string s) 
 5     {
 6         int n = s.size();
 7         // dp 数组全部初始化为 0
 8         // 在子串s[i..j]中，最长回文子序列的长度为dp[i][j]
 9         vector<vector<int>> dp(n, vector<int>(n, 0));
10         // base case
11         for (int i = 0; i < n; i++) dp[i][i] = 1;
12         // 反着遍历保证正确的状态转移
13         for (int i = n - 1; i >= 0; i--) 
14         {
15             for (int j = i + 1; j < n; j++) 
16             {
17                 // 状态转移方程
18                 if (s[i] == s[j])
19                     dp[i][j] = dp[i + 1][j - 1] + 2;
20                 else
21                     dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
22             }
23         }
24         // 整个 s 的最长回文子串长度
25         return dp[0][n - 1];
26     }
27 };