leetcode - 动态规划 - Part4

377. 组合总和 Ⅳ

题目描述

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。 

示例: 
nums = [1, 2, 3]
target = 4
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。

进阶： 
如果给定的数组中含有负数会怎么样？ 
问题会产生什么变化？ 
我们需要在题目中添加什么限制来允许负数的出现？ 

Related Topics 动态规划

题目分析：
由于数组中的数字可以重复使用，即每次的面临的选择为 $nums$ ，假如本次选择的数字为 $nums[i]$ ，则下次的目标成为 $target - nums[i]$ 。采用回溯算法：

class Solution:
    def __init__(self):
        self.res = 0

    def combinationSum4(self, nums: List[int], target: int) -> int:
        if target == 0:
            self.res += 1
            return
        if target < 0:
            return
        for num in nums:
            self.combinationSum4(nums, target-num)
        return self.res

考虑重复计算问题，使用备忘录：

class Solution:
    def __init__(self):
        self.memory = {}

    def combinationSum4(self, nums: List[int], target: int) -> int:
        return self.combinationSum4Core(nums, target)
        
    def combinationSum4Core(self, nums, target):
        if target == 0:
            return 1
        if target < 0:
            return 0
        if target in self.memory:
            return self.memory[target]
        res = 0
        for num in nums:
            res += self.combinationSum4(nums, target-num)
        self.memory[target] = res
        return res

回溯算法采用自顶向下的计算，既然有自顶向下的方案，那我们考虑自底向上的方法，也即动态规划。
由于每次选择面临的选择都是整个数组，所以我们的状态即为目标值。所以定义状态 $dp[i]$ 表示目标和为 $i$ 的组合数。则状态转移方程为 $dp[i] = sum([dp[i-num] for num in nums if i >= num])$ .

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        # dp[i] 表示和为i的组合数
        # dp[i] = sum([dp[i-num] for num in nums if i-num>=0])
        dp = [0] * (target+1)
        dp[0] = 1
        for i in range(1, target+1):
            dp[i] = sum([dp[i-num] for num in nums if i-num>=0])
        # print(dp)
        return dp[target]

139. 单词拆分

题目描述

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，
判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 

说明： 
拆分时可以重复使用字典中的单词。 
你可以假设字典中没有重复的单词。 

示例 1： 
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
 
示例 2： 
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
 注意你可以重复使用字典中的单词。
 
示例 3： 
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
Related Topics 动态规划

题目分析
此题和上一题 [377] 很像，只是这里我们的目标变成了字符串，每次面临的选择依然是整个字典。回溯即备忘录方法一致，动态规划方法稍微有点差异，我们这里状态定义为 $dp[i]$ 表示前 $i$ 个字符是否能被字典拆分。这样状态转移方程为 dp[i] = dp[i] or dp[i-len(word)] if i >= len(word) and s[i-len(word): i] == word。

1143. 最长公共子序列

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。 
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符
的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。 

示例 1: 
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。
 
示例 2: 
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc"，它的长度为 3。
 
示例 3: 
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。

提示: 
1 <= text1.length <= 1000 
1 <= text2.length <= 1000 
输入的字符串只含有小写英文字符。 
Related Topics 动态规划

题目分析
本题是典型的二维动态规划问题。对于字符 $s$ ，若 $s$ 在公共字符串中，则其同时在 $text1$ 和 $text2$ 中；若不在公共字符串中，则要么在 $text1$ 中，要么在 $text2$ 中。即 $s$ 在与不在 就为我们的选择。
直接看代码也更方便理解：

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n+1) for _ in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+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])
        # print(dp)
        return dp[m][n]

其中，状态各多设1个，省略初始化步骤。
主要疑问点是在 $dp[i][j-1], dp[i-1][j], dp[i-1][j-1]$ 中是否存在 $dp[i-1][j-1]$ 更大的情况，实际上通过下图可以看出来， $dp[i-1][j-1]$ 不会比 $dp[i][j-1], dp[i-1][j]$ 更大。

另外一个需要注意的是循环的顺序，

dp[i][j]

计算需要依赖于

dp[i][j-1], dp[i-1][j], dp[i-1][j-1]

。

300. 最长上升子序列

题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。 

示例: 
输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 

说明: 
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。 
你算法的时间复杂度应该为 O(n2) 。 

进阶: 
你能将算法的时间复杂度降低到 O(n log n) 吗? 
Related Topics 二分查找 动态规划

题目分析
对于这类序列长度问题，首先想到动态规划方法求解，其中状态为数组中的数字，选择为该数字能否添加进上升子序列。我们定义状态为 $dp[i]$ 表示以 $nums[i]$ 结尾的前缀序列能构成的最长上升子序列长度。则状态转移方程为 dp[i] = max([dp[j] if nums[i] > nums[j] else 0 for j in range(i)]) + 1。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        dp = [1] * n
        for i in range(1, n):
            dp[i] = max([dp[j] if nums[i] > nums[j] else 0 for j in range(i)]) + 1
        # print(dp)
        return max(dp)

我们再看一下进阶的问题，要求算法复杂度为 $O(n\,log\,n)$ ，则算法中可能用到二分查找类算法。我们维护一个数组 $tail$ ， $tail[i]$ 表示长度为 $i+1$ 的上升子序列的结尾数字。对于当前数字，如果其大于 $tail[-1]$ ，则我们将其添加到 $tail$ 末尾，若其小于 $tail[-1]$ ，则需要在 $tail$ 中找到第一个大于等于 $nums[i]$ 的数字，将其替换为当前数字。
需要注意的是，为什么这样做可以得到正确答案？
因为我们的 $tail[i]$ 表示长度为 $i+1$ 的上升子序列的结尾数字，这个定义非常关键。假如我们的数组为 [2, 5, 3, 7, 101, 4]，最后我们的 $tail$ 数组为 [2, 3, 4, 101]，疑问点可能就出在 $tail[2]$ 上，这个数字 $4$ 是我们原数组的最后一个数字，现在它在 $tail$ 的中间位置，看似这样形成的上升子序列不合理，但是其不影响最后长度的结果。假如我们考虑长度为 $3$ 的上升子序列，则以数字 $4$ 结尾的上升子序列结尾数字最小，在这种情形下，它才能在后面接更多的数字以形成更长的上升子序列。所以结果是正确的。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        tail = [nums[0]]
        for i in range(1, n):
            if nums[i] > tail[-1]:
                tail.append(nums[i])
            else:
                # 在tail里找到第一个大于等于nums[i] 的数字，进行替换
                low, high = 0, len(tail)-1
                while low < high:
                    mid = (low+high)//2
                    if tail[mid] < nums[i]:
                        low = mid + 1
                    else:
                        high = mid
                tail[high] = nums[i]
        # print(tail)
        return len(tail)

376. 摆动序列

题目描述

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。
第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。 

例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。
相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值
都是正数，第二个序列是因为它的最后一个差值为零。 

给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中
删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。 

示例 1: 
输入: [1,7,4,9,2,5]
输出: 6 
解释: 整个序列均为摆动序列。
 
示例 2: 
输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。 

示例 3: 
输入: [1,2,3,4,5,6,7,8,9]
输出: 2 

进阶: 
你能否用 O(n) 时间复杂度完成此题? 
Related Topics 贪心算法 动态规划

题目分析
和上一题 [300] 类似，本题也是求子序列长度，所以我们可以将状态定义为以 $nums[i]$ 结尾的前缀子序列 XX 最大长度。因为序列为摆动序列，大小交替，我们能否利用一个 $dp$ 数组来实现呢？上一题中，我们的状态转移方程为 dp[i] = max([dp[j] if nums[i] > nums[j] else 0 for j in range(i)]) + 1。本题中我们要实现的是对交替数字的判断，即 $nums[i]$ 究竟是大于还是小于 $nums[j]$ 依赖于以 $nums[j]$ 结尾的子序列最后是上升还是下降。如果只利用单个 $dp$ 数组，我们无法记录 $nums[j]$ 结尾的数组是上升还是下降的，于是考虑使用两个数组来进行记录。直接看代码：

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        up = [1] * n
        down  = [1] * n
        for i in range(1, n):
            up[i] = max([down[j] if nums[i] > nums[j] else 0 for j in range(i)]) + 1
            down[i] = max([up[j] if nums[i] < nums[j] else 0 for j in range(i)]) + 1
        # print(up)
        # print(down)
        return max(up+down)

其中 $up[i]$ 是记录以 $nums[i]$ 结尾是上升的子序列长度， $down[i]$ 是记录以 $nums[i]$ 结尾是下降的子序列长度。此时的时间复杂度为 $O(n^2)$ 。
关注进阶问题，需要用 $O(n)$ 的时间复杂度来解决问题。
我们同样利用两个数组，分别记录前 $i$ 个元素可以组成的上升和下降子序列长度。

针对元素 $nums[i]$ ，有以下3中情况

$nums[i] > nums[i-1]$ ，此时 $up[i] = down[i-1] + 1$

若 $down[i-1]$ 恰好以 $nums[i-1]$ 结尾，则 $up[i] = down[i-1] + 1$ 。
若 $down[i-1]$ 的结尾数字为 $nums[j]$ 且 $j < i-1$ ，则 $nums[j:i]$ 都为递增序列，所以 $down[i-1]$ 一直等于 $down[j]$ ，此时也满足 $up[i] = down[i-1] + 1$ 。

$nums[i] < nums[i-1]$ ，此时 $down[i] = up[i-1] + 1$
$nums[i] = nums[i-1]$ ，保持不变

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        up = [1] * n
        down  = [1] * n
        for i in range(1, n):
            if nums[i] > nums[i-1]:
                up[i] = down[i-1] + 1
                down[i] = down[i-1]
            elif nums[i] < nums[i-1]:
                down[i] = up[i-1] + 1
                up[i] = up[i-1]
            else:
                up[i] = up[i-1]
                down[i] = down[i-1]
        return max(up[n-1], down[n-1])

由于 $up$ 和 $down$ 都是依赖前一次的值，所以这里还可以进行空间度复杂度的优化。

174. 地下城游戏

题目描述

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。
我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。 

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。 
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表
示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数
的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。 

为了尽快到达公主，骑士决定每次只向右或向下移动一步。 

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。 

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。 

-2 (K)  -5     10
-3      -10    30
 3       1    -5(P)

说明: 
骑士的健康点数没有上限。 
任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。 
Related Topics 二分查找 动态规划

题目分析
面对这种网格路径问题，首先想到利用二维动态规划进行求解。我们按照常规思路设定状态为骑士走到位置 $(i, j)$ 所需要的的最少初始健康点数。假如是求路径和，则我们的状态转移方程为 $dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + dungeon[i][j]$ ，由于本题中是需要求得初始健康点数，那我们是不是可以将状态转移方程写成 $dp[i][j] = max(1, min(dp[i-1][j], dp[i][j-1]) +dungeon[i][j])$ 呢？答案是否定的。这是因为题目中要求我们求得走到右下角所需最小健康点数，不管当前是在什么位置，我们的目标都是 $(m-1, n-1)$ ，所以 $dp[i][j]$ 依赖的不是 $dp[i-1][j],dp[i][j-1]$ ，而是依赖于 $dp[i+1][j],dp[i][j+1]$ ，同时我们的状态需要定义为骑士从位置 $(i, j)$ 走到右下角所需的初始健康点数，否则 $dp[i][j]$ 不满足无后效性的要求。
有了状态转移方程，接下来需要确认 $base case$ ，按照题目要求，骑士最低健康点数必须大于0，当到达位置 $(m-1, n-1)$ 时，其依赖于 $dp[m][n-1],dp[m-1][n]$ ，而在位置 $(m, n-1)$ 和 $(m-1, n)$ 时，骑士的最小健康点数为1。

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        # dp[i][j] 表示从位置 (i, j) 达到右下角所需的最低健康点数
        m, n = len(dungeon), len(dungeon[0])
        if m == 0 or n == 0:
            return 1
        dp = [[float('inf')] * (n+1) for _ in range(m+1)]
        dp[m-1][n] = dp[m][n-1] = 1
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
        # print(dp)
        return dp[0][0]

53. 最大子序和

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 

示例: 
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 
进阶: 
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。 
Related Topics 数组 分治算法 动态规划

题目分析
对于这类子数组的问题，状态定义一般为以 $nums[i]$ 结尾的子数组XX。由此，本题 $dp[i]$ 即可定义为以 $nums[i]$ 结尾的子数组的最大和。如果 $nums[i]$ 能够加在 $nums[i-1]$ 后形成更大的和，则 dp[i] = dp[i-1]+nums[i]，否则， $nums[i]$ 单独形成一个更大的和，即 dp[i] = nums[i]。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # dp[i] 表示nums[i]结尾的子数组的最大和
        n = len(nums)
        if n == 1:
            return nums[0]
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(nums[i], dp[i-1]+nums[i])
        # print(dp)
        return max(dp)

131. 分割回文串

题目描述

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 
返回 s 所有可能的分割方案。 

示例: 
输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
] 
Related Topics 回溯算法

题目分析
由于最后输出的结果为分割的具体方案，因此需要使用回溯算法。对于每个拆分结果的判断，我们可以尝试使用动态规划进行数据预处理。其中 $dp[i][j]$ 表示 $s[i: j+1]$ 是否为回文字符串。所以状态转移方程为 dp[i][j] = dp[i+1][j-1] and s[i]==s[j]。

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        # 动态规划预处理数据
        # dp[i][j] 表示 s[i:j+1] 是否为回文串
        dp = [[False] * n for _ in range(n)]
        # 初始化
        for i in range(n):
            dp[i][i] = True
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                if j - i > 1:
                    dp[i][j] = dp[i+1][j-1] and s[i] == s[j]
                else:
                    dp[i][j] = s[i] == s[j]
        # print(dp)
        # 取得结果
        res = []
        self.getResult(s, len(s), 0, dp, [], res)
        return res
    
    def getResult(self, s, n, start, dp, path, res):
        if start == n:
            res.append(path[:])
            return
        for i in range(start, n):
            if not dp[start][i]:
                continue
            path.append(s[start: i+1])
            self.getResult(s, n, i+1, dp, path, res)
            path.pop()

132. 分割回文串 II

题目描述

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。 
返回符合要求的最少分割次数。 

示例: 
输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

Related Topics 动态规划

题目分析
最简单的方案莫过于采用【131】题的解法，最后计算最短的分割方案即可得出结果。但是这种方法复杂度高，且由于不需要返回最终结果，对于这类最小次数问题，尝试采用动态规划进行求解。假如定义 $dp[i]$ 为子字符串 $s[0: i+1]$ 分割成回文串的最小分割次数，那我们的状态转移方程又该怎么写呢？对于子字符串 $s[0: i+1]$ ，候选分割方案为 $1...i$ 的任意位置，假如分割位置为 $j$ ，需要满足什么条件呢？由于 $dp[j]$ 为子字符串 $s[0:j+1]$ 分割成回文子串的最少分割次数，如果 $s[j+1: i+1]$ 也为回文串，那我们就找到了一个结果—— $dp[j]+1$ 。我们遍历 $1...i$ 的任意位置，然后求取最小值即为我们的结果。

class Solution:
    def minCut(self, s: str) -> int:
        # dp[i] 表示将子字符串 s[0: i+1] 分割成回文字符串的最少分割次数
        # dp[i] = min([dp[j]+1 if s[j+1:i+1] 是回文串 else n for j in range(i)])
        n = len(s)
        dp = [n] * n
        dp[0] = 0
        for i in range(1, n):
            if self.isPalindrome(s, 0, i):
                dp[i] = 0
                continue
            dp[i] = min([dp[j]+1 if self.isPalindrome(s, j+1, i) else n for j in range(i)])
        # print(dp)
        return dp[n-1]

    def isPalindrome(self, s, start, end):
        while start < end:
            if s[start] != s[end]:
                return False
            start += 1
            end -= 1
        return True

其中判断回文串还能采用记忆化的方式，以避免重复计算。又联想到【131】中的数据预处理方案，本题中我们依然可以采用。

115. 不同的子序列

题目描述

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

题目数据保证答案符合 32 位带符号整数范围。 

示例 1： 
输入：S = "rabbbit", T = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
 
示例 2： 
输入：S = "babgbag", T = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 S 中得到 "bag" 的方案。 
(上箭头符号 ^ 表示选取的字母)
babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^ 
Related Topics 字符串 动态规划

题目分析
本题可以看着两个字符串的匹配问题。所以对于 $s[i]$ 和 $t[j]$ 的匹配有两种情况：要么匹配，要么不匹配。根据题目要求，对于匹配的情况，我们可以选择该字符，若不匹配，我们只能不选择该字符。

class Solution:
    def __init__(self):
        self.res = 0

    def numDistinct(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        self.numDistinctCore(s, t, n, 0, m, 0)
        return self.res

    def numDistinctCore(self, s, t, n, i, m, j):
        if m == j:
            self.res += 1
            return
        if i >= n:
            return
        # 选择该字符
        if s[i] == t[j]:
            self.numDistinctCore(s, t, n, i+1, m, j+1)
        # 不选择该字符
        self.numDistinctCore(s, t, n, i+1, m, j)

有了回溯解法，那动态规划就相对简单了。定义 $dp[i][j]$ 表示 $t[:j]$ 在 $s[:i]$ 的子序列中出现次数。

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        if m < n:
            return 0
        # dp[i][j] 表示s[:i] 的子串中 t[:j] 出现的次数
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(m+1):
            dp[i][0] = 1
        for i in range(1, m+1):
            for j in range(1, min(n, i)+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]
        # print(dp)
        return dp[m][n]

参考

https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-zhi-zui-chang-gong-gong-zi-xu-lie/