[数据结构与算法]LeetCode：动态规划中的子序列问题

PS. 本文是参考代码随想录做的一些笔记，完整版本请戳链接，非常好的教程！

本文列举了一些经典题目，特别是编辑距离，基本上的题目解题思路都是一样的，可以说是一个路子。

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度。

位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。所以：if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1)。

注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度。
        if len(nums) == 0: return 1

        dp = [1] * len(nums)

        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        return max(dp)

674. 最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

贪心：遇到nums[i + 1] > nums[i]的情况，num就+1，否则num为1，记录num的最大值就可以了。

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        res = 1  # 记录结果
        num = 1  # 记录实时的子序列个数
        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                num += 1
                res = max(res, num)
            else:
                num = 1
            
        return res

动态规划：

dp[i]：以下标i为结尾的数组的连续递增的子序列长度为dp[i]。

注意这里的定义，一定是以下标i为结尾，并不是说一定以下标0为起始位置。

递推公式：如果 nums[i + 1] > nums[i]，那么以 i+1 为结尾的数组的连续递增的子序列长度 一定等于 以i为结尾的数组的连续递增的子序列长度 + 1 。即：dp[i + 1] = dp[i] + 1。

一个for循环就可以解决了，代码如下：

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        # dp[i]：以下标i为结尾的数组的连续递增的子序列长度为dp[i]
        dp = [1] * len(nums)
        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                dp[i] = dp[i - 1] + 1
        
        return max(dp)

718. 最长重复子数组

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

dp数组以及下标的含义：dp[i][j]：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。

根据dp[i][j]的定义，dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1。根据递推公式可以看出，遍历i 和j 要从1开始！

代码如下：

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        # dp[i][j]：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]
        m, n = len(nums1) + 1, len(nums2) + 1
        dp = [[0 for _ in range(n)] for _ in range(m)]
        res = 0

        for i in range(1, m):
            for j in range(1, n):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                res = max(res, dp[i][j])
        
        return res

滚动数组：我们可以看出dp[i][j]都是由dp[i - 1][j - 1]推出。那么压缩为一维数组，也就是dp[j]都是由dp[j - 1]推出。也就是相当于可以把上一层dp[i - 1][j]拷贝到下一层dp[i][j]来继续用。此时遍历B数组的时候，就要从后向前遍历，这样避免重复覆盖。

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1) + 1, len(nums2) + 1
        dp = [0 for _ in range(n)]
        res = 0

        for i in range(1, m):
            for j in range(n - 1, 0, -1):  # 遍历B数组的时候，就要从后向前遍历，这样避免重复覆盖。
                if nums1[i - 1] == nums2[j - 1]:
                    dp[j] = dp[j - 1] + 1
                else:
                    dp[j] = 0  # 这里不相等的时候要有赋0的操作
                res = max(res, dp[j])
        
        return res

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

本题和上一题的区别在于这里不要求是连续的了，但要有相对顺序，即：“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]。

递推公式主要有两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同

• 如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
• 如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。

即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])。

其余的和上一题差不多了，代码是实现如下：

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
        res = 0

        for i in range(1, len(text1) + 1):
            for j in range(1, len(text2) + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                
                res = max(res, dp[i][j])
        
        return res

1035. 不相交的线

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：

• nums1[i] == nums2[j]
• 且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。以这种方法绘制线条，并返回可以绘制的最大连线数。

绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且直线不能相交！直线不能相交，这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。想一想公共子序列指的是啥？指的是相对顺序不变！这么分析完之后，其实可以发现本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！好了，本题结束，把上一题的题解copy过来就行了！

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        res = 0

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                res = max(res, dp[i][j])
        return res

53. 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。其中，子数组 是数组中的一个连续部分。

贪心：题目中要求的使最大和的连续子数组，那么对数组nums从左往右遍历求和，一旦发现和为负了，其实当前的数和之前的数都不选取。

什么意思呢？如果 -2 1 在一起，计算起点的时候，一定是从1开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = -float("inf")  # 会有负数，所以初始化为最小的数
        total_sum = 0

        for i in range(len(nums)):
            total_sum += nums[i]
            res = max(total_sum, res)
            if total_sum < 0: total_sum = 0
        
        return res

动态规划：

dp[i]：包括下标i之前的最大连续子序列和为dp[i]。

dp[i]只有两个方向可以推出来：

• dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
• nums[i]，即：从头开始计算当前连续子序列和

一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i])。

从递推公式可以知道，dp[0]需要初始化，很明显，dp[0]=nums[0]。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0] * len(nums) 
        dp[0] = nums[0]

        for i in range(1, len(nums)):
            dp[i] = max(nums[i], dp[i - 1] + nums[i])
        
        return max(dp)

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度。

注意这里是判断s是否为t的子序列。即t的长度是大于等于s的。

在确定递推公式的时候，考虑如下两种操作：

• if (s[i - 1] == t[j - 1])：t中找到了一个字符在s中也出现了。那么dp[i][j] = dp[i - 1][j - 1] + 1，因为找到了一个相同的字符，相同子序列长度自然要在dp[i-1][j-1]的基础上加1
• if (s[i - 1] != t[j - 1])：此时相当于t要删除元素，t如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与t[j - 2]的比较结果了，即：dp[i][j] = dp[i][j - 1]。

从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。根据递推公式，初始化为0就可。

有个问题，在定义dp[i][j]含义的时候为什么要表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。因为这样的定义在dp二维矩阵中可以留出初始化的区间，如下图。

dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度，所以如果dp[s.size()][t.size()]与字符串s的长度相同说明：s与t的最长相同子序列就是s，那么s 就是 t 的子序列。

代码实现如下：

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        dp = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]

        for i in range(1, len(s) + 1):
            for j in range(1, len(t) + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = dp[i][j - 1]
        
        return dp[len(s)][len(t)] == len(s)

115. 不同的子序列【hard】

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，“ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

这一类问题，基本是要分析两种情况

• s[i - 1]与t[j - 1]相等
• s[i - 1]与t[j - 1]不相等

当s[i - 1] 与 t[j - 1]相等时，此时有两种前置状态可以跳到dp[i][j]

• 用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。（也就是让i和j都前进一步）
• 不用s[i - 1]来匹配，个数为dp[i - 1][j]。（只让j前进一步，为什么不单独让i前进一步呢，因为我们是在单独选s中的字符）

这里有一个问题，为什么还要考虑不用s[i - 1]来匹配，都相同了指定要匹配啊。可以考虑这种场景： s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。当然也可以用s[3]来匹配，即：s[0]s[1]s[3]组成的bag。

所以当s[i - 1] 与 t[j - 1]相等时，dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]。

当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配，即：dp[i - 1][j]。所以递推公式为：dp[i][j] = dp[i - 1][j]。

从递推公式中可以看出dp[i][0]和dp[0][j]是一定要初始化的。

• 根据dp数组的定义，dp[i][0]表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数。那么dp[i][0]一定都是1，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1。
• 再来看dp[0][j]，dp[0][j]表示空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数。那么dp[0][j]一定都是0，s如论如何也变成不了t。
• 最后来看一个dp[0][0]，dp[0][0]应该是1，空字符串s，可以删除0个元素，变成空字符串t。

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
        
        for i in range(len(s) + 1):
            dp[i][0] = 1

        for i in range(1, len(s) + 1):
            for j in range(1, len(t) + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j]
        
        return dp[len(s)][len(t)]

583. 两个字符串的删除操作

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。每步 可以删除任意一个字符串中的一个字符。

方法一：

dp[i][j]：以i-1为结尾的字符串word1，和以j-1为结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

递推公式，考虑如下两种情况：

• 当word1[i - 1] 与 word2[j - 1]相同的时候，很显然，dp[i][j] = dp[i - 1][j - 1]。
• 当word1[i - 1] 与 word2[j - 1]不相同的时候，有三种情况：
  • 情况一：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
  • 情况二：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
  • 情况三：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2

最后当然是取最小值，所以当word1[i - 1] 与 word2[j - 1]不相同的时候，递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1})

从递推公式中，可以看出，dp[i][0]和dp[0][j]是一定要初始化的。dp[i][0]：word2为空字符串，以i-1为结尾的字符串word1要删除多少个元素，才能和word2相同呢，很明显dp[i][0] = i。dp[0][j]同理。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0 for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]

        for i in range(len(word1) + 1): dp[i][0] = i
        for j in range(len(word2) + 1): dp[0][j] = j

        for i in range(1, len(word1) + 1):
            for j in range(1, len(word2) + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j - 1] + 2, min(dp[i][j - 1], dp[i - 1][j]) + 1)
        
        return dp[len(word1)][len(word2)]

方法二：【最长相同子序列】

本题和最长公共子序列那道题是基本相同的，只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0 for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]

        for i in range(1, len(word1) + 1):
            for j in range(1, len(word2) + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        return len(word1) + len(word2) - 2 * dp[len(word1)][len(word2)]

72. 编辑距离（🧡🧡）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

在确定递推公式的时候，首先要考虑清楚编辑的几种操作：

if (word1[i - 1] == word2[j - 1])
    不操作
    
if (word1[i - 1] != word2[j - 1])
    增
    删
    换

if(word1[i - 1] == word2[j - 1])那么说明不用任何编辑，dp[i][j] 就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1]。

if(word1[i - 1] != word2[j - 1])，此时就需要编辑了，如何编辑呢？

• 操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1与j-1为结尾的word2的最近编辑距离再加上一个操作。即dp[i][j] = dp[i - 1][j] + 1。
• 操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1与j-2为结尾的word2的最近编辑距离再加上一个操作。即 dp[i][j] = dp[i][j - 1] + 1。
• 操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增加元素，那么以下标i-2为结尾的word1与j-2为结尾的word2的最近编辑距离 加上一个替换元素的操作。即dp[i][j] = dp[i - 1][j - 1] + 1。

综上，当 if (word1[i - 1] != word2[j - 1]) 时取最小的，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1。

思考一个问题，为什么这里没有添加元素呢？

• word2添加一个元素，相当于word1删除一个元素，例如word1 = "ad"，word2 = "a"，word1删除元素'd'和word2添加一个元素'd'，变成word1="a",word2="ad"最终的操作数都一样！

现在对dp数组进行初始化。根据递推公式，dp[i][0]和 dp[0][j]都是必须要初始化的。那么dp[i][0] 和 dp[0][j] 表示什么呢？dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近的编辑距离。那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i。同理dp[0][j] = j。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0 for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]

        for i in range(len(word1) + 1):
            dp[i][0] = i
        
        for j in range(len(word2) + 1):
            dp[0][j] = j
        
        for i in range(1, len(word1) + 1):
            for j in range(1, len(word2) + 1):
                if word1[i - 1] == word2[j - 1]:  # 不用做任何编辑
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1
        return dp[len(word1)][len(word2)]

647. 回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中的由连续字符组成的一个序列。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

动态规划：

dp[i][j]：表示区间范围[i,j]（注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

在确定递推公式时，就要分析如下几种情况。整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。

• 当s[i]与s[j]不相等，dp[i][j]一定是false。
• 当s[i]与s[j]相等时，有如下三种情况
  • 情况一：下标i与j相同，同一个字符例如a，当然是回文子串
  • 情况二：下标i与j相差为1，例如aa，也是回文子串
  • 情况三：下标：i与j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1与j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

dp[i][j]初始化为false，这很显然。

从递推公式中可以看出，情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。

代码实现为：

class Solution:
    def countSubstrings(self, s: str) -> int:
        dp = [[False for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s) - 1, -1, -1):
            for j in range(i, len(s)):
                if s[i] == s[j]:
                    if j - i <= 1:
                        dp[i][j] = True
                        res += 1
                    elif dp[i + 1][j - 1]:
                        res += 1
                        dp[i][j] = True
        
        return res

双指针：

动态规划的空间复杂度是偏高的，事实上这道题双指针法更简单。

首先确定回文串，就是找中心然后向两边扩散看是不是对称的就可以了。在遍历中心点的时候，要注意中心点有两种情况。

• 一个元素可以作为中心点
• 两个元素也可以作为中心点

class Solution:
    def countSubstrings(self, s: str) -> int:
        res = 0
        for i in range(len(s)):
            res += self.extend(s, i, i)  # 以i为中心点
            res += self.extend(s, i, i + 1)  # 以i和i+1为中心点
        return res

    def extend(self, s, i, j):
        res = 0
        while i >= 0 and j < len(s) and s[i] == s[j]:
            i -= 1
            j += 1
            res += 1
        return res

5. 最长回文子串

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

和上一题非常类似，代码如下：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0  # 左闭右闭区间
        for i in range(len(s)):
            start1, end1 = self.extend(s, i, i)
            if end1 - start1 > end - start:  # 选取最长的字串，更新起始和终止索引
                start, end = start1, end1
                
            start2, end2 = self.extend(s, i, i + 1)
            if end2 - start2 > end - start:  # 选取最长的字串，更新起始和终止索引
                start, end = start2, end2
        
        return s[start : end + 1]      
    
    def extend(self, s, i, j):
        while i >= 0 and j < len(s) and s[i] == s[j]:
            i -= 1
            j += 1
        return i + 1, j - 1  # 注意这里，在最后一次满足条件进入循环，i和j多处理了一次

516. 最长回文子序列

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

在判断回文子串的题目中，关键逻辑就是看s[i]与s[j]是否相同。

• 如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2。
• 如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
  • 加入s[j]的回文子序列长度为dp[i + 1][j]。
  • 加入s[i]的回文子序列长度为dp[i][j - 1]。

那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。

考虑当i和j相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2。可以看出递推公式是计算不到i和j相同时候的情况。所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。

由递推公式可以看出，遍历i的时候一定要从下到上遍历，这样才能保证，下一行的数据是经过计算的。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp = [[0 for _ in range(len(s))] for _ in range(len(s))]

        for i in range(len(s)):
            dp[i][i] = 1
        
        for i in range(len(s) - 1, -1, -1):
            for j in range(i + 1, len(s)):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        
        return dp[0][len(s) - 1]