步骤一、确定状态:
确定dp数组及下标含义
dp[i][j] 表示的是区间范围[i,j] 的子串是否是回文子串
步骤二、推断状态方程:
如果s[i] != s[j]， 当前的dp[i][j] = False
如果s[i] == s[j]， 这时候还得分三种情况:
下标i与j指向的是同一个下标， 也就是同一个字符，这时候肯定是True
下标i和j相差一个位置，比如aa， 这时候也是True
如果i和j相差大于1个位置的时候， 比如abca， abba，这种，dp[i][j]是不是回文子串 又得看dp[i+1][j-1]了。
所以此时d[i][j] = dp[i+1][i-1]
步骤三、规定初始条件:
初始条件:
全局初始化False， 而对角线初始化为True。
步骤四、计算顺序:
遍历i的时候一定要从下到 上遍历，这样才能保证，下 一行的数据是经过计算的。 即逆向遍历行，正向遍历列
class Solution:def longestPalindrome(self, s: str) -> str:if len(s) == 1:return s# dp数组定义，初始化dp = [[False for _ in range(len(s))] for _ in range(len(s))]# 对角线元素初始化for i in range(len(s)):dp[i][i] = 1left, right, max_length = 0, 0, 0for i in range(len(s) - 1, -1, -1):for j in range(i, len(s)):if s[j] == s[i]:if j - i <= 1 or dp[i+1][j-1]:dp[i][j] = True# 更新结果，在得到[i,j]区间内是否有回文子串的时候，保存左右边界if dp[i][j] and j - i + 1 > max_length:max_length = j - i + 1left = iright = jreturn s[left:right + 1]
如果觉得《121. Leetcode 5. 最长回文子串 (动态规划-子序列问题)》对你有帮助，请点赞、收藏，并留下你的观点哦！
