lc516 最长回文子序列

给定长度为n的字符串s，求最长回文子序列的长度。
1<=n<=1000

区间dp，记dp[i][j]表示区间[i,j]能构成的最长回文串的长度，根据s[i]跟s[j]是否相等进行转移。

class Solution {
public:
    int dp[1005][1005];
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        for (int d = 1; d <= n; d++) {
            for (int i = 0; i+d <= n; i++) {
                int j = i+d-1;
                if (d == 1) {
                    dp[i][j] = 1;
                } else if (d == 2) {
                    dp[i][j] = s[i] == s[j] ? 2 : 1;
                } else if (s[i] == s[j]) {
                    dp[i][j] = 2 + dp[i+1][j-1];
                } else {
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        return dp[0][n-1];
    }
};