C++ | dp | #最长回文子串#
最长回文子串
https://www.nowcoder.com/practice/12e081cd10ee4794a2bd70c7d68f5507
dp解法
以adadd为例
第一个循环记录字母本身，如a开始到a，为1，d开始到d，为1
第二个循环记录相邻的字母是否会回文，如ad不行记录为0，dd可以，记录为2
第三个循环dp，对于dp[i][j]，也就是从第i个到第j个字符串是否回文，首先要第i个字符和第j个字符相等，然后要第i+1个字符到第j-1个字符是回文，如果满足，则等于dp[i+1][j-1]+2
第四个循环寻找最长回文
#include <iostream>
#include <string>
using namespace std;
int main(void) {
string s;
cin >> s;
int n = s.size();
int m = 0;
int dp[350][350]; //分别表示开始和终止，用矩阵一半的地方表示
for (int i = 0; i < n; i++)
dp[i][i] = 1;
for (int i = 0; i < n - 1; i++)
dp[i][i + 1] = s[i + 1] == s[i] ? 2 : 0;
for (int i = n - 3; i >= 0; i--)
for (int j = i + 2; j < n; j++)
dp[i][j] = s[i] == s[j] && dp[i + 1][j - 1] ? dp[i + 1][j - 1] + 2 : 0;
for (int i = 0; i < n; i++)
for (int j = i; j < n; j++)
m = m > dp[i][j] ? m : dp[i][j];
cout << m;
return 0;
}
查看17道真题和解析
