当前位置：首页 > news >正文

别再暴力搜索了！用C++动态规划5分钟搞定PTA最长回文子串（附完整代码）

news 2026/5/4 9:32:54

暴力搜索 vs 动态规划：5分钟攻克PTA最长回文子串难题

每次刷算法题遇到"最长回文子串"这类经典问题时，你是否也经历过这样的痛苦：写了个暴力解法，信心满满地提交，结果——"Time Limit Exceeded"！别担心，这不是你算法能力的问题，而是方法的选择问题。今天我们就来彻底解决这个困扰无数刷题者的经典难题。

1. 为什么暴力搜索会超时？

暴力解法看似直观，但它的时间复杂度高达O(n³)。对于长度为1000的字符串（PTA题目上限），这意味着需要进行近10亿次操作！现代计算机虽然快，但在算法竞赛的严格时间限制下，这样的复杂度显然无法接受。

让我们看看暴力解法的典型实现思路：

枚举所有可能的子串（双重循环）
对每个子串检查是否为回文（第三重循环）
记录最长的回文子串长度

// 暴力解法示例（不推荐） bool isPalindrome(string &s, int start, int end) { while (start < end) { if (s[start++] != s[end--]) return false; } return true; } int longestPalindrome(string s) { int maxLen = 0; for (int i = 0; i < s.size(); i++) { for (int j = i; j < s.size(); j++) { if (isPalindrome(s, i, j)) { maxLen = max(maxLen, j - i + 1); } } } return maxLen; }

2. 动态规划的降维打击

动态规划(DP)能将时间复杂度优化到O(n²)，空间复杂度也是O(n²)。对于n=1000的情况，这只需要约100万次操作，比暴力解法快了近1000倍！

2.1 DP状态定义

我们定义dp[i][j]表示字符串从第i个字符到第j个字符是否为回文子串。这是一个布尔型的二维数组。

关键点：

当i == j时，单个字符自然是回文，dp[i][j] = true
当j == i+1时，只需比较s[i]和s[j]是否相等

2.2 状态转移方程

动态规划的核心在于找到状态之间的转移关系。对于回文子串问题，状态转移方程如下：

dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]

这个方程的意思是：只有当首尾字符相同，并且去掉首尾后的子串也是回文时，整个子串才是回文。

2.3 边界条件处理

在实际编码中，我们需要特别注意边界条件：

所有长度为1的子串都是回文
长度为2的子串只需比较两个字符是否相同
填充dp表时需要按子串长度从小到大进行

3. 完整DP解决方案

下面是一个可以直接提交PTA的C++实现，包含了完整的初始化和状态转移逻辑：

#include <iostream> #include <cstring> using namespace std; const int MAXN = 1010; bool dp[MAXN][MAXN]; int main() { string s; getline(cin, s); int n = s.size(); if (n <= 1) { cout << n << endl; return 0; } int maxLen = 1; // 初始化长度为1的子串 for (int i = 0; i < n; i++) { dp[i][i] = true; } // 初始化长度为2的子串 for (int i = 0; i < n - 1; i++) { if (s[i] == s[i+1]) { dp[i][i+1] = true; maxLen = 2; } } // 处理长度大于2的子串 for (int len = 3; len <= n; len++) { for (int i = 0; i + len - 1 < n; i++) { int j = i + len - 1; if (s[i] == s[j] && dp[i+1][j-1]) { dp[i][j] = true; maxLen = len; } } } cout << maxLen << endl; return 0; }

4. 常见错误与优化技巧

4.1 易犯错误

数组越界：在访问dp[i+1][j-1]时，确保i+1 ≤ j-1
初始化遗漏：忘记初始化长度为1和2的子串情况
遍历顺序错误：必须按子串长度从小到大填充dp表
空间浪费：使用N×N的二维数组时，确保N足够大（PTA中N=1010足够）

4.2 空间优化技巧

标准的DP解法需要O(n²)空间，但我们可以优化到O(n)空间。这是通过观察状态转移只依赖于前一行的结果来实现的：

int longestPalindrome(string s) { int n = s.size(); if (n <= 1) return n; int maxLen = 1; vector<bool> prev(n, false), curr(n, false); for (int i = n - 1; i >= 0; i--) { for (int j = i; j < n; j++) { if (i == j) { curr[j] = true; } else if (j == i + 1) { curr[j] = (s[i] == s[j]); } else { curr[j] = (s[i] == s[j]) && prev[j-1]; } if (curr[j] && j - i + 1 > maxLen) { maxLen = j - i + 1; } } prev = curr; } return maxLen; }