题解 | #最长回文子串#

#include <iostream>
using namespace std;
#include <string>
#include <vector>
int main() {
    string str;
    getline(cin, str);
    vector<vector<bool>> dp(str.size(), vector<bool>(str.size(), false));
    int maxl = 0;
    for (int i = str.size() - 1; i >= 0; i--) {
        for (int j = i; j < str.size(); j++) {
            if (str[i] == str[j]) {
                if(j-i <= 1){
                    dp[i][j] = true;
                }
                else if(dp[i+1][j-1]){
                    dp[i][j] = true;
                }
            }
            if(dp[i][j]){
                maxl = max(j-i+1,maxl);
            }

        }
    }
    cout << maxl << endl;
}

也是回文子串的变种，

在动态规划寻找回文子串的过程中顺便记录长度