题解 | #密码截取#一维动态规划

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool isduicheng(string& s, int start, int end) {
    while (start <= end) {
        if (s[start++] != s[end--]) {
            return false;
        }
    }
    return true;
}

int main() {
    string s;
    getline(cin, s);
    vector<int> dp(s.size() + 1, 0);
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= s.size(); i++) {
        dp[i] = dp[i - 1];
        for (int j = 0; j <= i - dp[i - 1]; j++) {
            if (isduicheng(s, j, i)) {
                int len = i - j + 1;
                dp[i] = max(len, dp[i - 1]);
                break;
            }
        }

    }
    cout << dp[s.size()];
}
// 64 位输出请用 printf("%lld")