[动态规划]最长回文子串-对于动态转移循环顺序的思考
最长回文子串标题
给你一个字符串 s，找到 s 中最长的回文子串。
样例
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解答思路
本题使用dp的思想
[*]为了得到回文子串的开始和结尾所以要得到两个值，所以dp数组选择二维数组，dp表示字符串i位置到j位置的子串是否为回文串
[*]那么我们就研究动态转移方程，思考dp从dp来(可以想到，"babab"由"aba"来，由于添加的'b'和'b'相等，所以"babab"继承了"aba"的回文性质),那么dp是否为回文串和字符串i和j位置的字符是否相等息息相关，结果是由dp决定
[*]所以得到转移条件和方程 如果 j - i >= 3 && 字符串s == s 那么 dp = dp
易错点
平常的动态规划都是对dp数组直接按行循环，但是这道题不行，因为我们发现dp = dp这个状态意味着每个位置都由他的左下角决定，如果按行来，那么左下角还没有状态导致错误
所以我们要按行来进行状态转移
代码
func longestPalindrome(s string) string {
dp := make([][]bool,len(s))
for i := range dp {
dp = make([]bool,len(s))
dp = true
}
be,end := 0,0
maxlen := -1
for j := 0;j < len(s);j++ {
for i := 0; i < j;i++ {
if s != s {
dp = false
}else {
if j - i >= 3 {
dp = dp
}else{
dp = true
}
}
if dp == true && j - i > maxlen {
maxlen = j - i
be,end = i,j
}
}
}
return string(s)
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]