这是一道非常经典的动态规划的题目，题目如下：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
我们可以先自己列举几个例子，先看一看规律：
当输入 s 字符串长度为 1 时，它肯定是一个回文，如 "a"。
当输入的 s 字符串长度为 2 时，需要判断第一个和最后一个字符是否相同才能判断是不是回文，如 "aa" , "bb" 是回文, "ab" , "ba" 不是回文。
当输入的 s 字符串长度为 3 时，判断条件与 2 相同，即 "aba" , "bab" 是回文。
当 s 字符串长度大于 3 时，我们则需要判断第一个和最后一个字符是否相同，且除去第一个和最后一个字符串后，剩余的子序列是不是回文，若剩余的子序列也是回文，则 s 也是回文。如 "abba" , "ababa" 是回文。
假设 i 为字符串 s 的子序列第一个字符串的索引, j 为 s 子序列最后一个字符串的索引, 用 dp 来记录 s 字符串的某个子序列是否是回文，如 dp[i][j]= 1 则代表 s[i: j + 1] （若 s 为 "aba" , i = 0, j = 1 则 s[i: j + 1] 为 "ab"） 是回文，dp[i][j]= 0 则相反。
则有动态规划方程：
将上面的规划方程转换为代码则为：
class Solution:
def longestPalindrome(self, s: str) -> str:
len_s = len(s)
dp = [[0] * len_s for _ in range(len_s)]
# 注意这里不能写成 [[0] * len_s] * len_s，这样生成的内嵌列表都是引用
si, sj = 0, 0
for j in range(len_s):
for i in range(j + 1):
dis = j - i
if dis <= 2 and s[i] == s[j]:
dp[i][j] = 1
if dis > sj - si:
si, sj = i, j
elif s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = 1
if dis > sj - si:
si, sj = i, j
return s[si: sj + 1]
《97 Things Every Programmer Should Know》 - Act with Prudence
Todo 或者 技术债的记录。Stackedit 一个免费在线的 markdown 编辑器，可以自动将写好的文件同步到 Google Drive , Github , Gitlab , CouchDB 。
虽然还是 Typora 比较好用，但是相比前者它不能同步云存储。
“I will learn it when I need it – 我会在我需要的时候再学“！ - 程序员的谎谬之言还是至理名言？