题解 | #最长回文子序列#

dp[i][j]表示字符串s的下标范围[i,j]内的最长回文子序列的长度，假设字符串s的长度为n，当时，才满足dp[i][j]>0，否则dp[i][j]=0。

初始化：由于任何长度为1的子序列都是回文子序列，所以对于任意的，都有dp[i][i]=1

状态转移：

当i<j时，计算dp[i][j]需要考虑s[i]和s[j]相等和不相等的情况：

1. 如果s[i]==s[j]，则s的下标范围[i+1,j-1]内的最长回文子序列，在该最长回文子序列的首位分别添加s[i]和s[j]，得到了下标范围[i,j]的最长回文子序列，所以 dp[i][j] = dp[i+1][j-1] + 2
2. 如果s[i]≠s[j]，s[i]和s[j]不可能同时作为一个回文子序列的首尾，所以dp[i][j] = max( dp[i+1][j], dp[i][j-1])

#include <iostream>
using namespace std;
const int N = 1001;
//dp[i][j]: 字符串 s的[i~j]的子串的最长回文子序列的长度,答案：dp[0][n-1]
int dp[N][N];
int main() {
    string s;
    cin >> s;
    int n = s.size();
    for(int i = n-1; i>-1; i--){
        dp[i][i] = 1;  
        for(int j=i+1;j<n;j++){
            if(s[i]==s[j]){  // s[i]==s[j]说明这个字符可以加入到s的子串s[i~j]的最长回文子序列中
                dp[i][j] = dp[i+1][j-1]+2;
            }else{
                dp[i][j] = max(dp[i][j-1],dp[i+1][j]);
            }
        }
    }
    cout << dp[0][n-1];
    return 0;
}
// 64 位输出请用 printf("%lld")