5. 最大回文子串

题目： Leetcode 5.最大回文子串 （中等） （二刷）

解题思路

该题目使用暴力法肯定是不行的哦
（Leetcode给出的测试案例，我是用动态规划都达到了4000+ms，更别提暴力法了，时间复杂度都爆掉了）

接下来我们来看一下动态规划如何解题

---

一、何为动态规划？（DP）

动态规划：简而言之，就是当前的值需要依赖前一个值计算求得，进而求得全局最优解。

注：全局最优，局部可不一定最优哦，要和贪心算法有所区别开来

---

二、如何使用动态规划？

我总结了5大步骤：

① 定义状态：首先，要明白我要求什么，需要哪些参数值。即定义元素的基本含义，不如我要求最大个数，最多路径走法等等

② 建立状态转移方程： 这一步，要明确两个状态之间的关系，一般数学建模转化成二维数组（有些题目可以优化空间复杂度，一维数组就够了），

写法一般为dp[i][j] = ? ,这个问号就是需要跟前面求得的值进行联系。

③ 设定初始值（考虑边界情况）：这一步就是将特殊情况和一般情况分开来。

④ 选出结果：根据我要求的东西，计算得出最后的结果。

⑤ 状态压缩：这一步一般是优化空间复杂度的，比如将O(n²) => O(n)或者O(n) => O(1)。

--- #### **三、结合本题进行分析**

① 定义状态 ： 根据题目要求，要求最长的回文子串，所以我需要设定一个长度值max_count,
其次，为了切出该子串，我还需要知道该子串的起始索引，因此还需设定一个起始位置索引值start_index。
这样子串长度就等于 s[start_index:start_index+max_count]

② 建立状态转移方程： 求一个子串，可以切分其首尾，首：j,尾：i，那么如果表示呢？我们就可以根据i,j来建模，
新建一个二维数组dp[j][i],表示以j为首，i为尾的字符串，用bool类型来表示它是否是回文子串。

③设定初始值：默认的，我们将dp所有元素设置为False，这里我采用列表推导，相比for循环效率要高很多。具体原因这里提一下：
主要是因为列表推导中直接使用了LIST_APPEND字节码，实现append追加功能，而for，每次循环都要先载入append的属性，然后再回调其方法，肯定会慢一些。

④选出结果： 根据题目要求，求子串，那么使用切片就行了s[start_index:start_index+max_count]。

---

代码：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 动态规划
        m = len(s)
        if m <= 1:
            return s
        dp = [[False for _ in range(m)] for _ in range(m)]
        max_count = 1
        start_index = 0
        for i in range(1,m):
            for j in range(0,i):
                if s[j] == s[i]:
                    if i-j+1 <= 3:
                        dp[j][i] = True
                    else:
                        dp[j][i] = dp[j+1][i-1]
                else:
                    dp[j][i] = False
                if dp[j][i]:
                    if i-j+1 > max_count:
                        max_count = i-j+1
                        start_index = j
        return s[start_index:start_index+max_count]