leetcode516 Longest Palindromic Subsequence

思路:

区间dp。

实现:

 1 class Solution 
 2 {
 3 public:
 4     int longestPalindromeSubseq(string s) 
 5     {
 6         int n = s.length();
 7         int dp[1001][1001];
 8         for (int i = 0; i < n; i++)
 9         {
10             dp[i][i] = 1;
11             if (i != n - 1) dp[i][i + 1] = (s[i] == s[i + 1] ? 2 : 1);
12         }
13         for (int i = n - 1; i >= 0; i--)
14         {
15             for (int j = i + 2; j < n; j++)
16             {
17                 if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
18                 else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
19             }
20         }
21         return dp[0][n - 1];
22     }
23 };