别再暴力搜索了！用C++动态规划5分钟搞定PTA最长对称子串（附完整代码）
从暴力搜索到动态规划：5分钟掌握PTA最长对称子串高效解法
在算法竞赛和编程测试中，字符串处理一直是高频考点。PTA（Programming Teaching Assistant）平台上的"最长对称子串"问题，看似简单却暗藏玄机。许多初学者面对这类问题时，第一反应往往是暴力枚举所有可能的子串并逐一验证，这种解法虽然直观，但时间复杂度高达O(n³)，当字符串长度达到1000时，计算量将变得难以接受。
动态规划（Dynamic Programming, DP）正是为解决这类重叠子问题而生的利器。通过巧妙地构建状态转移方程和填表策略，我们可以将时间复杂度优化到O(n²)，这在PTA等对运行时间有严格限制的平台上至关重要。本文将带你一步步拆解DP解法，理解其核心思想，并最终给出可直接提交的优化代码。
1. 问题分析与暴力解法
对称子串（即回文串）是指正读反读都相同的字符串片段。给定一个长度为n的字符串，我们需要找出其中最长的回文子串。让我们先看看最直观的暴力解法：
- 枚举所有可能的子串（共n(n+1)/2个）
- 对每个子串检查是否为回文
- 记录遇到的最大回文长度
// 暴力解法示例代码（仅作对比，不推荐实际使用） bool isPalindrome(const string &s, int left, int right) { while (left < right) { if (s[left++] != s[right--]) return false; } return true; } int longestPalindromeBruteForce(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; }这种解法的主要问题在于重复计算。例如，检查"abba"时，我们已经知道"bb"是回文，但在暴力解法中这个信息没有被有效利用。
2. 动态规划解法原理
动态规划的核心思想是利用已解决的子问题来构建更大问题的解。对于回文串问题，我们可以定义：
- 状态定义：
dp[i][j]表示字符串从索引i到j的子串是否为回文 - 边界条件：
- 单个字符总是回文：
dp[i][i] = true - 两个相同字符也是回文：
dp[i][i+1] = (s[i] == s[i+1])
- 单个字符总是回文：
- 状态转移方程：
- 如果
s[i] == s[j]且dp[i+1][j-1]为真，则dp[i][j] = true - 否则
dp[i][j] = false
- 如果
这种解法之所以高效，是因为它利用了回文串的对称性质：一个大回文串去掉首尾字符后仍然是回文串。
3. 动态规划实现详解
让我们逐步实现这个DP解法。关键点在于填表顺序：由于计算dp[i][j]需要知道dp[i+1][j-1]，我们应该按子串长度从小到大进行填充。
#include <iostream> #include <cstring> using namespace std; int longestPalindromeDP(string s) { int n = s.size(); if (n < 2) return n; // 初始化DP表 bool dp[n][n]; memset(dp, 0, sizeof(dp)); 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; } } // 检查长度>=3的子串 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; } } } return maxLen; }注意：在实际PTA提交时，由于部分编译器不支持变长数组(VLA)，建议使用固定大小的数组如
dp[1001][1001]，或者使用vector容器。
4. 复杂度分析与优化空间
让我们对比不同解法的时间和空间复杂度：
| 解法类型 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力枚举 | O(n³) | O(1) | 小规模数据(n<100) |
| 动态规划 | O(n²) | O(n²) | 中等规模数据(n≤1000) |
| 中心扩展 | O(n²) | O(1) | 需要节省空间时 |
虽然DP解法已经将时间复杂度优化到O(n²)，但我们还可以进一步优化空间复杂度。观察状态转移方程可以发现，计算dp[i][j]只需要知道下一行的dp[i+1][j-1]，因此可以使用滚动数组将空间复杂度降到O(n)。
int longestPalindromeOptimized(string s) { int n = s.size(); if (n < 2) return n; bool dp[2][n]; memset(dp, 0, sizeof(dp)); int maxLen = 1; // 初始化长度为1和2的子串 for (int i = 0; i < n; ++i) { dp[0][i] = true; if (i < n - 1 && s[i] == s[i+1]) { dp[1][i] = true; maxLen = 2; } } // 检查长度>=3的子串 for (int len = 3; len <= n; ++len) { int cur = (len - 1) % 2; int prev = len % 2; for (int i = 0; i + len - 1 < n; ++i) { int j = i + len - 1; if (s[i] == s[j] && dp[prev][i+1]) { dp[cur][i] = true; maxLen = len; } else { dp[cur][i] = false; } } } return maxLen; }5. PTA提交完整代码与测试用例
以下是可直接提交到PTA平台的完整代码，包含了边界条件处理和输入输出：
#include <iostream> #include <cstring> using namespace std; const int MAXN = 1001; bool dp[MAXN][MAXN]; int main() { string s; getline(cin, s); int n = s.size(); if (n < 2) { cout << n << endl; return 0; } memset(dp, 0, sizeof(dp)); 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; } } // 检查长度>=3的子串 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; }常见测试用例：
- 空字符串：输入
""，输出0 - 单个字符：输入
"a"，输出1 - 全相同字符：输入
"aaaa"，输出4 - 无回文子串（除单字符）：输入
"abcde"，输出1 - 混合字符：输入
"abacdfgdcaba"，输出3（"aba"） - 最长回文在末尾：输入
"xyzmalayalam"，输出9（"malayalam"）
6. 算法思维拓展与应用
掌握动态规划解最长回文子串后，我们可以进一步思考：
如何输出最长回文子串本身而不仅是长度？
- 在DP过程中记录最长回文的起始和结束位置
- 最后用
substr方法提取该子串
更高效算法：
- Manacher算法可以在O(n)时间内解决问题
- 适用于特别长的字符串（n>10000）
变种问题：
- 统计所有回文子串的数量
- 查找最长回文子序列（不要求连续）
- 分割字符串使每个部分都是回文
// 输出最长回文子串的扩展实现 string longestPalindromeString(string s) { int n = s.size(); if (n < 2) return s; bool dp[n][n]; memset(dp, 0, sizeof(dp)); int start = 0, maxLen = 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; start = i; maxLen = 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; if (len > maxLen) { start = i; maxLen = len; } } } } return s.substr(start, maxLen); }在实际编程竞赛中，理解问题本质并选择合适算法比单纯记忆模板更重要。动态规划虽然有时难以理解，但通过像回文串这样的经典问题练习，可以逐步培养出对状态定义和转移方程的敏感度。