516. Longest Palindromic Subsequence ---------M ~~~~

 Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"

Output:

4

One possible longest palindromic subsequence is "bbbb".

 

Example 2:
Input:

"cbbd"

Output:

2

One possible longest palindromic subsequence is "bb".

 

Constraints:

• 1 <= s.length <= 1000
• s consists only of lowercase English letters.

A:

就是经典的DP。  每次加入一个来。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        vector<vector<int>> V(n, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            V[i][i] = 1;
        }
        for (int end = 1; end < n; end++) {
            for (int start = end-1; start >=0; start--) {
                if (s[start] == s[end]) {
                    V[start][end] = 2 + (start + 1 == end ? 0 : V[start+1][end-1]);
                }
                else {
                    V[start][end] = start + 1 == end ? 1 : max(V[start][end-1], V[start+1][end]);
                }
            }
        }
        return V[0][n - 1];
    }
};

Errors：

这道题，最需要注意的是，如果s[start] != s[end] , 我们需要考虑2种情况， 一种是， end往前一个。 一种是 start 往后一个。