题解 | #密码截取# 区间dp
密码截取
https://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1
#include <iostream>
using namespace std;
const int N = 2550;
bool dp[N][N];
int main() {
string s;
cin >> s;
int n = s.length(), start = 0, maxLength = 1;
for(int i = 0; i < n; i++) {
dp[i][i] = true;
if(i < n-1 && s[i] == s[i+1]) {
dp[i][i+1] = true;
start = i;
maxLength = 2;
}
}
for(int len = 3; len <= n; len++) {
for(int i = 0; i <= n-len; i++) {
int j = i + len - 1;
if(s[i] == s[j] && dp[i+1][j-1]) {
dp[i][j] = true;
start = i;
maxLength = len;
}
}
}
cout << maxLength;
return 0;
}
查看30道真题和解析