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

f[i][j]为范围从i到j的最长回文子序列

当s[i] == s[j]时 f[i + 1][j - 1] + 2

当s[i] != s[j]时 max(f[i][j - 1], f[i + 1][j])

初始化：当i不断向右移动j不断向左移动，最终会到中间i == j的位置，这个时候是需要初始化 f[i][i] = 1

由于 要从i + 1 推出 i 从j - 1推出 j 所以i要-- j要++ 即i从后往前遍历的顺序 而j必须要时刻大于i 因为[i,j]范围

#include <iostream>
using namespace std;

const int N = 1010;
int f[N][N];

int main() {
    string s;
    cin >> s;
    int res = 0;
    for (int i = 0; i < s.size(); i ++) f[i][i] = 1;
    for (int i = s.size() - 1; i >= 0; i --) {
        for (int j = i + 1; j < s.size(); j ++) {
            if (s[i] == s[j]) f[i][j] = f[i + 1][j - 1] + 2;
            else f[i][j] = max(f[i + 1][j], f[i][j - 1]);
        }
    }
    res = f[0][s.size() - 1];
    cout << res << endl;

}