题解 | #密码截取#

#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 m = 0;
    for (int i = str.size() - 1; i >= 0; i--) {
        for (int j = i ; j < str.size(); j++) {
            if (str[i] == str[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] && (j-i+1)>m){
                    m = j-i+1;
                }
            }

        }
    }

    cout << m << endl;

}

题目没讲的太具体，我还以为是最长回文子序列，结果提交后是最长回文子串问题

附上笔记：

3.1 回文子串

3.1.1 问题描述

• 给定一个字符串，找出其中所有的回文子串（左右对称的串）

3.1.2 dp[I][J]的含义

• [i,j]这个范围内子串是否为回文子串（true/false）

3.1.3 递推公式

• if(s[i] == s[j])情况一 i==j a情况二 i和j相差1 aa情况三 i和j相差大于1 依赖于dp[i+1][j-1]

if (s[i] == s[j]) {
    if (j - i <= 1) { // 情况一 和 情况二
        result++;
        dp[i][j] = true;
    } else if (dp[i + 1][j - 1]) { // 情况三
        result++;
        dp[i][j] = true;
    }
}

• result就是统计回文子串的数量

3.1.4 数组初始化

• dp[i][j] = false

3.1.5 遍历顺序

• dp[i][j]依赖于dp[i + 1][j - 1]从底部往上，从左往右j>=i,只有右上一半有数据

for (int i = s.size() - 1; i >= 0; i--) {  // 注意遍历顺序
    for (int j = i; j < s.size(); j++) {
        if (s[i] == s[j]) {
            if (j - i <= 1) { // 情况一 和 情况二
                result++;
                dp[i][j] = true;
            } else if (dp[i + 1][j - 1]) { // 情况三
                result++;
                dp[i][j] = true;
            }
        }
    }
}