如何优化动态规划最长回文子串算法中的动态转移循环顺序？

本文共计600个文字，预计阅读时间需要3分钟。

最长回文子串 + + 给你一个字符串s，找到s中s+中 最长的回文子串。+ 样例 + 示例 1：+ 输入：s=babad+ 输出：bab+ 解释：aba 同样是符合题意的答案。+ 示例 2：+ 输入：s=cbbd+ 输出：bb

最长回文子串

标题

给你一个字符串 s，找到 s 中最长的回文子串。

样例

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

来源：力扣（LeetCode）
链接：leetcode.cn/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答思路

本题使用dp的思想

1. 为了得到回文子串的开始和结尾所以要得到两个值，所以dp数组选择二维数组，dp[i][j]表示字符串i位置到j位置的子串是否为回文串
2. 那么我们就研究动态转移方程，思考dp[i][j]从dp[i + 1][j - 1]来(可以想到，"babab"由"aba"来，由于添加的'b'和'b'相等，所以"babab"继承了"aba"的回文性质),那么dp[i][j]是否为回文串和字符串i和j位置的字符是否相等息息相关，结果是由dp[i + 1][j - 1]决定
3. 所以得到转移条件和方程 如果 j - i >= 3 && 字符串s[i] == s[j] 那么 dp[i][j] = dp[i + 1][j - 1]

易错点

平常的动态规划都是对dp数组直接按行循环，但是这道题不行，因为我们发现dp[i][j] = dp[i + 1][j - 1]这个状态意味着每个位置都由他的左下角决定，如果按行来，那么左下角还没有状态导致错误
所以我们要按行来进行状态转移

代码

func longestPalindrome(s string) string { dp := make([][]bool,len(s)) for i := range dp { dp[i] = make([]bool,len(s)) dp[i][i] = true } be,end := 0,0 maxlen := -1 for j := 0;j < len(s);j++ { for i := 0; i < j;i++ { if s[i] != s[j] { dp[i][j] = false }else { if j - i >= 3 { dp[i][j] = dp[i + 1][j - 1] }else{ dp[i][j] = true } } if dp[i][j] == true && j - i > maxlen { maxlen = j - i be,end = i,j } } } return string(s[be:end + 1]) }