题解 | #密码截取#

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

int main() {
    string s;
    int res = 1;
    cin >> s;
    int n = s.size();
    // 代表以下标为n结尾的码串的最长有效密码传长度
    vector<vector<int>> dp(n, vector<int>(2, 1));
    // [i][0]代表有效密码串不完全相同的情况，[i][1]代表有效密码串完全相同的情况


    for (int i = 1; i < n; i++) {
        if (s[i] == s[i - 1]) {
            dp[i][1] = dp[i - 1][1] + 1;
            res = max(res, dp[i][1]);
        } else {
            int tmp1 = 1, tmp2 = 1;
            if (i - 1 - dp[i - 1][1] >= 0 && s[i] == s[i - 1 - dp[i - 1][1]]) {
                tmp1 = dp[i - 1][1] + 2;
            }
            if (i - 1 - dp[i - 1][0] >= 0 && s[i] == s[i - 1 - dp[i - 1][0]]) {
                tmp2 = dp[i - 1][0] + 2;
            }
            dp[i][0] = max(tmp1,tmp2);
            res = max(res, dp[i][0]);
        }
    }
    cout << res << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

动态规划的核心是定义过程量 以及 考虑过程量之间的关系。

本题对于对称 分成了全部相同和 非全部相同两种情况进行考虑， 并考虑了他们之间的关系。