动态规划简明教程 - 3
内容提要
本文介绍了使用动态规划解决“最长回文子串”问题的方法。通过暴力搜索、记忆化搜索和动态规划逐步优化算法，动态规划的核心在于状态转移方程，利用子串特性判断回文，最终实现高效解决方案。
延伸解读
从暴力到动态规划的优化思路
文章展示了解决最长回文子串问题的渐进优化路径：先实现暴力搜索，再尝试记忆化搜索，最后推导动态规划。这种顺序符合自顶向下的思考过程，能降低直接推导状态转移方程的难度。暴力搜索通过枚举所有子串并检测回文，虽然简单但可能超时；记忆化搜索旨在缓存结果，但文章指出其性能反而下降，原因是递归参数组合多样，缓存未有效利用。动态规划则通过定义状态和转移方程，系统化地计算所有子串，避免重复检测。
记忆化搜索为何性能下降
文章分析指出，记忆化搜索在最长回文子串问题上并未提升性能，反而因额外开销变慢。关键原因在于递归调用 isPalindromeMemo 时，参数 i 和 j 的组合几乎每次不同，导致备忘录很少命中，缓存形同虚设。同时，递归调用和备忘录内存分配增加了负担。这提醒我们，记忆化搜索并非总是优化，其效果取决于子问题是否重复。对于回文检测，子问题重叠度低，因此动态规划的自底向上填表方式更合适。
动态规划的状态转移方程解析
文章详细推导了回文子串的状态转移方程。对于长度大于2的回文串，去掉首尾字符后仍是回文串，因此当 s[i]==s[j] 时，F(i,j) 取决于 F(i+1,j-1)。边界条件包括：长度为1的子串必为回文；长度为2的子串当两字符相等时为回文。合并后得到完整方程。算法实现时，先初始化所有单字符为回文，然后按子串长度递增枚举，确保计算 F(i,j) 时 F(i+1,j-1) 已计算。这种自底向上的填表方式保证了正确性和效率。
Q&A
动态规划如何解决最长回文子串问题？
动态规划通过定义状态转移方程，利用子串特性判断回文，从而高效计算最长回文子串。
暴力搜索方法是如何找到最长回文子串的？
暴力搜索通过检测每个子串是否为回文，遍历字符串以找到最长的回文子串。
记忆化搜索在解决最长回文子串问题时有什么局限性？
记忆化搜索在某些情况下性能可能下降，因为递归调用可能导致过多的内存使用和方法调用。
动态规划的状态转移方程是什么？
状态转移方程为：F(i, j) = F(i+1, j-1)，当s[i] == s[j]时，且边界条件为F(i, i)和F(i, i+1)。
如何实现动态规划算法来找到最长回文子串？
通过建立状态转移表，初始化所有长度为1的子串为回文，逐步计算并更新最大回文长度和起始位置。
最长回文子串的单元测试是如何设计的？
单元测试通过多种输入字符串验证函数的输出是否符合预期，包括空字符串、单字符字符串和含重复字符的字符串。
