代码随想录算法训练营第二十天 | 动态规划系列9,10,11,12

编辑距离(子序列)系列就记住一点，dp数组的定义是：以…结尾的…

300 最长递增子序列

未看解答自己编写的青春版

我只会写，dp数组含义是，以 i 结尾的子串的最大长度，这样的话，虽然是一维dp数组，但要两层循环遍历。

注意，这里“以 i 结尾”是一个非常重要的点，也是本题的关键，只有这样才能有判断“递增”的条件。

“连续”同理。

本题依然是按照动规五部曲来思考的，真好用。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        # 初始化初始化
        dp = [1]*n
        dp[0] = 1
        for i in range(1,n):
            for j in range(i):
                if nums[i] > nums[j] :
                    dp[i] = max(dp[i],dp[j]+1)
        #优化，将max操作替换为一个每次跟随更新的result变量
        return max(dp)

1
2
3
4
5
6
7
8
9
10
11
12
13

本题的重点在于，要遍历当前下标 j 前面的每一个点，去求取最大值。

重点

没想到代码随想录的思路和我的一样，所以根本思想在于明确，必须是以 i 为结尾，来定义。

这道题在自己写的时候，初始化那里写错了，找了一上午才找到，应该初始化为全1，而非全0，并且本题的值，是和每个位置的初始化均有关，而非像之前的题一样，只和dp[0]或者dp[1]有关。

另外，之前自己没做过，一维dp数组，在状态转移的时候，还要去遍历每一个前面状态的，所以在想到这个思路了，充满了怀疑和犹豫。

其实本题的递推公式中，不是找 i 和 i-1 的关系，而是找的是 i 和 j 的关系，j 是小于 i 的某个数，这样思考之后，遍历 i 之前的每个状态，就是很自然的事情了。

这种对子序列操作的，都是类似的思路，不要限制自己去思考 i-1 和 i ，怪不得我之前做的这些关于序列的动态规划题目，在思考递推关系上都有点怪。

另外，本题需要明确的是，第一层遍历为 i , 表示下标 i 包括 i 之前的序列的最长递增子序列的长度，第二层遍历，为遍历 i 之前的所有下标 j ，在第二层遍历中，前序倒序都无所谓！

代码随想录的代码

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)
        dp = [1] * len(nums)
        result = 1
        for i in range(1, len(nums)):
            for j in range(0, i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
            result = max(result, dp[i]) #取长的子序列
        return result
1
2
3
4
5
6
7
8
9
10
11
12

我的代码(当天晚上理解后自己编写)

过。

674 最长连续递增序列

未看解答自己编写的青春版

在上一题的基础上稍作改动即可。

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        n = len(nums)
        # 初始化初始化
        dp = [1]*n
        dp[0] = 1
        # 这里，是用来统计最大值的，避免之后做max操作
        # 但是也要注意初始值的给定，应该是1而不是0
        res = 1
        for i in range(1,n):    
            if nums[i] > nums[i-1] :
                dp[i] = dp[i-1]+1
            res = max(res,dp[i])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

但是有一个要注意的点，为了避免最后对dp数组求max，设置一个res变量，注意初始值的设定，应该是1而不是0！

重点

dp数组的定义，以及变量初始化的值。

dp数组含义是，以 i 结尾的最长递增子序列的长度。

代码随想录的代码

动态规划：

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        result = 1
        dp = [1] * len(nums)
        for i in range(len(nums)-1):
            if nums[i+1] > nums[i]: #连续记录
                dp[i+1] = dp[i] + 1
            result = max(result, dp[i+1])
        return result
1
2
3
4
5
6
7
8
9
10
11

贪心法：

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        result = 1 #连续子序列最少也是1
        count = 1
        for i in range(len(nums)-1):
            if nums[i+1] > nums[i]: #连续记录
                count += 1
            else: #不连续，count从头开始
                count = 1
            result = max(result, count)
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13

我的代码(当天晚上理解后自己编写)

过

718 最长重复子数组

未看解答自己编写的青春版

二维dp数组版本，需要注意的点，都写在注释中了。这道题一个最最需要注意的地方，子数组，就是连续的子序列，之前没有这个概念。

def findLength(self, nums1: List[int], nums2: List[int]) -> int:
    # 二维dp数组，最直接的想法，dp[i][j]
    # 代表nums1为前i个，以第i个结尾，nums2为前j个,以第j个结尾

    # 根据错误示例判断，这题要连续？
        n = len(nums1)
        m = len(nums2)
        res = 0
        # 初始化，全0即可，而且由于递推函数的关系，这一圈0应该是要加的
        # 这里的声明初始化注意，n为行数，m为列数
        dp = [[0]*(m+1) for _ in range(n+1)]
        
        for i in range(1,n+1):
            for j in range(1,m+1):
                if nums1[i-1] == nums2[j-1] :
                    dp[i][j] = dp[i-1][j-1]+1
                else :
                    dp[i][j] = 0
                res = max(res,dp[i][j])
            

        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

想用一维dp实现，因为总感觉是可以的，但是自己写出来的代码逻辑很乱，没有掌握根本思想。下面列出错误代码

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
    # 二维dp数组，最直接的想法，dp[i][j]
    # 代表nums1为前i个，以第i个结尾，nums2为前j个,以第j个结尾

    # 根据错误示例判断，这题要连续？
        n = len(nums1)
        m = len(nums2)
        res = 0
        # 初始化，全0即可，而且由于递推函数的关系，这一圈0应该是要加的
        # 这里的声明初始化注意，n为行数，m为列数
        dp = [0]*(m+1)
        
        for i in range(1,n+1):
            for j in range(m,0,-1):
                if nums1[i-1] == nums2[j-1] :
                    dp[j] = max(dp[j-1]+1,dp[j])
                else :
                    dp[j] = 0
                res = max(res,dp[j])
            

        return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

想用双指针法实现，但是发现涉及状态太多，双指针法根本做不了，这道题只能用DP。错误代码如下

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
  
        n = len(nums1)
        m = len(nums2)
        res = 0
        cleft = 0
        cright = 0
        count = 0
        while cleft < n or cright < m :
            left = cleft % n 
            right = cright % m
            if nums1[left]==nums2[right]:
                count += 1
                cleft += 1
                cright += 1
            else :
                if cleft < n :
                    cleft += 1
                else :
                    cleft += 1
                    cright += 1
                count = 0
            res = max(res,count)
            if cleft == n :
                count = 0

        cleft = 0
        cright = 0
        count = 0
        while cleft < n or cright < m :
            left = cleft % n 
            right = cright % m
            if nums1[left]==nums2[right]:
                count += 1
                cleft += 1
                cright += 1
            else :
                if cright < m :
                    cright += 1
                else :
                    cleft += 1
                    cright += 1
                count = 0
            res = max(res,count)
            if cright == m :
                count = 0
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

重点

注意题目中说的子数组，其实就是连续子序列。

二维DP数组的方法，比较好理解，而且我觉得在意义设置上，没有代码随想录里讲的那么需要注意细节吧，很直观就想到需要二维DP，因为题目要求连续，那么意义就是以 i 为结尾的子序列，又因为当前状态依靠前面状态给出，自然要多加一行一列为前置状态，初值为0也是自然的。如果不要求连续，DP意义就可以是包括 i 之前的子序列。

当 num1[i] 不等于 num2[j] 时，dp[i][j] = 0 是自然的，是无所谓的，因为当前的最大值已经被 res 变量记录了。并且，根据dp数组的定义，是以 i 为结尾的子序列，以 j 为结尾的子序列，是有“结尾”条件的，那么现在结尾的两个元素不相等，结果自然就是0.

遍历顺序，先遍历哪个数组都无所谓。

需要理解的点是，使用一维DP数组的情况。

懂了懂了，将二维DP数组降为一维DP数组的方法，一维DP数组的意义不要去纠结！

如果按照题目定义，最显然的是二维DP数组，那么能不能将其压缩为一维数组，是和在二维状态下，由递推公式的表达形式决定的。如果 i j 只依赖于 i-1 j j-1 (或者 i-1 i j-1)，那么就可以做压缩。如果和 i-1 j-1 i j 都有关，那么就不能进行压缩！

如果对DP数组进行压缩，就不要去想DP数组的含义了，想不明白的，因为其本身是二维DP，只不过做了状态压缩！

所以如果想写一维DP，肯定是先写二维，再通过递推逻辑，改成一维！

根据上下两个，一个错误的代码，一个正确的代码，打印了dp数组看了看，对上述结论更加有信心了，本题中 dp[j] 不能和自己比较，这在二维DP下是显而易见的，因为这代表着 dp[i][j] 和 dp[i-1][j]， 这两者在本题中，是没有直接的关系的！

所以一定不要按照，二维的DP数组的含义，去揣测一维，比如把 dp[j] 揣测为，nums2中以第 j 个字符为结尾的最长重复子数组，这是错误的，因为不知道如何表示 nums1 中相对应的子数组。

代码随想录的代码

动态规划：

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        dp = [[0] * (len(B)+1) for _ in range(len(A)+1)]
        result = 0
        for i in range(1, len(A)+1):
            for j in range(1, len(B)+1):
                if A[i-1] == B[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                result = max(result, dp[i][j])
        return result

1
2
3
4
5
6
7
8
9
10
11

动态规划：滚动数组

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        dp = [0] * (len(B) + 1)
        result = 0
        for i in range(1, len(A)+1):
            for j in range(len(B), 0, -1):
                if A[i-1] == B[j-1]:
                    dp[j] = dp[j-1] + 1
                else:
                    dp[j] = 0 #注意这里不相等的时候要有赋0的操作
                result = max(result, dp[j])
        return result

1
2
3
4
5
6
7
8
9
10
11
12
13

我的代码(当天晚上理解后自己编写)

1143 最长公共子序列

未看解答自己编写的青春版

和上一题依然有相似之处，这次不要求连续了，改一下递推关系即可。

同时 DP 数组的含义也要做出更改，dp[i][j] 是 第一个字符串第 i 个字符之前，包括 i , 第二个字符串第 j 个字符之前，包括 j , 的最长公共子序列。

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = len(text2)
        # dp定义，前i个，前j个字符之内的，最长公共子序列

        dp = [[0]*(n+1) for _ in range(m+1)]

        res = 0

        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1]==text2[j-1]:
                # 这里为什么不用考虑dp[i-1][j] dp[i][j-1] ？ 因为根据dp的定义,dp[i-1][j-1]最多就比
                # dp[i-1][j] dp[i][j-1]中的最大者小1，所以加上1之后，就是最大值。
                    dp[i][j] = dp[i-1][j-1]+1
                else :
                # 这个对比关系，我在上一题就想到了，但是上一题要求连续，这样递推不符合DP数组的定义
                # 本题就是这样的，如果不等，就各个维度退后一维
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
                res = max(res,dp[i][j])

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

发现不需要 res 变量，改进版本

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m = len(text1)
        n = 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])
               
        return dp[m][n]     
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

从递推关系上分析，应该是不能写出一维滚动DP数组的形式。

重点

代码随想录的分析，和我自己的分析，基本一致。

经过本题之后明确：子串代表连续，子序列代表不连续

代码随想录的代码

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        len1, len2 = len(text1)+1, len(text2)+1
        dp = [[0 for _ in range(len1)] for _ in range(len2)] # 先对dp数组做初始化操作
        for i in range(1, len2):
            for j in range(1, len1): # 开始列出状态转移方程
                if text1[j-1] == text2[i-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11

我的代码(当天晚上理解后自己编写)

1035 不相交的线

本题的本质就是：求两个数组的最长公共子序列

未看解答自己编写的青春版

为什么我感觉和上一题没有区别，求的也是最长公共子序列，直接代码复制过来。

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n = len(nums2)

        dp = [[0]*(n+1) for _ in range(m+1)]

        

        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])
               
        return dp[m][n]   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

重点

做了上一题再做这题，思路真的很顺畅，几乎不需要思考，后面要学会的是，如何在空白情况下，想到本题求的就是最长公共子序列。

只要元素相对顺序不变，最长公共子序列，连接的线，就是不会相交的。

代码随想录的代码

class Solution:
    def maxUncrossedLines(self, A: List[int], B: List[int]) -> int:
        dp = [[0] * (len(B)+1) for _ in range(len(A)+1)]
        for i in range(1, len(A)+1):
            for j in range(1, len(B)+1):
                if A[i-1] == B[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 dp[-1][-1]
1
2
3
4
5
6
7
8
9
10

我的代码(当天晚上理解后自己编写)

53 最大子序和

未看解答自己编写的青春版

首先明确又是连续的问题，那么 dp 的定义中，就是要以第 i 个元素为结尾的最大子序和。

本题也是，dp[i] 以第 i 个元素为结尾。

其次明确递推关系，最大和应该与前一个dp值有关，如果前一个dp值足够大，那么nums[i]为负数也无所谓，后面可能依旧有正值，但是如果前一个dp值是负值，那么就不能再继续了。

这样想来似乎又可以写一版代码，以dp[i-1]为判断条件。

class Solution:
    def maxSubArray(self, nums):
        n = len(nums)
        # dp数组的定义，以第 i 个数组结尾的连续子数组的最大和，包括 i 
        # 根据定义以及递推关系，可以想到，dp数组的初始化就是nums数组
        dp = nums.copy()
        res = nums[0]

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

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13

但其实像上面那一版代码，没有必要一开始就给 dp 赋好初值，因为后面还要遍历，copy()操作又慢的要死，list[:] 操作本质上也是copy。

class Solution:
    def maxSubArray(self, nums):
        n = len(nums)
        # dp数组的定义，以第 i 个数组结尾的连续子数组的最大和，包括 i 
        # 根据定义以及递推关系，可以想到，dp数组的初始化就是nums数组
        dp = [0]*n
        dp[0] = nums[0]
        res = nums[0]

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

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

以dp[i-1]为判断条件的代码：

class Solution:
    def maxSubArray(self, nums):
        n = len(nums)
        # dp数组的定义，以第 i 个数组结尾的连续子数组的最大和，包括 i 
        # 根据定义以及递推关系，可以想到，dp数组的初始化就是nums数组
        dp = nums.copy()
        res = nums[0]

        for i in range(1,n):
            if dp[i-1] > 0 :
                dp[i] = dp[i-1]+nums[i]
            res = max(res,dp[i])

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

延续上个想法，dp数组的初始化可以进行相应更改：

class Solution:
    def maxSubArray(self, nums):
        n = len(nums)
       
        dp = [0]*n
        dp[0] = nums[0]
        res = nums[0]

        for i in range(1,n):
            if dp[i-1] < 0 :
                dp[i] = nums[i]
            else :
                dp[i] = dp[i-1]+nums[i]
            res = max(res,dp[i])

        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

在上面编写不同代码时，发现copy()函数很慢

上面我自己写了三版代码，前两版速度差不多，都是只打败了10%，最后一版竟然是打败了40%。

重点

这道题之前在贪心算法的时候做过，先来复习一下贪心，直接粘贴代码：

class Solution:
    def maxSubArray(self, nums):
        result = float('-inf')  # 初始化结果为负无穷大
        count = 0
        for i in range(len(nums)):
            count += nums[i]
            if count > result:  # 取区间累计的最大值（相当于不断确定最大子序终止位置）
                result = count
            if count <= 0:  # 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
                count = 0
        return result
1
2
3
4
5
6
7
8
9
10
11

代码随想录的代码

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [0] * len(nums)
        dp[0] = nums[0]
        result = dp[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1] + nums[i], nums[i]) #状态转移公式
            result = max(result, dp[i]) #result 保存dp[i]的最大值
        return result
1
2
3
4
5
6
7
8
9

我的代码(当天晚上理解后自己编写)

下面就进入“编辑距离”系列了，一共四道题，注意题目的递进学习！

编辑距离的题目，均为设定二维DP数组，dp[i][j] 的定义，均为以 i 为结尾的word1 , 和以 j 为结尾的word2 。

编辑距离系列，一定要理解的是，下标减一等价于删除操作，看清楚题目描述的，是，谁是谁的子序列，这意味着对谁做删除，而不需要对谁做删除。

392 判断子序列

未看解答自己编写的青春版

方法一：双指针法，这题就能用双指针做了，因为题目明确说明，判断 s 是否为 t 的子串，所以双指针在移动时，就是先移动 t 的指针，只有两个字母相等时，才同时移动两个指针，同样本题也可以先做一个小剪枝，都写在代码中了。

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        left = 0
        right = 0
        n = len(s)
        m = len(t)
        if m < n :
            return False
        while left < n and right < m :
            if s[left] == t[right] :
                left += 1
                right += 1
            else :
                right+=1

        if left == n and right <= m :
            return True
        else :
            return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方法二：动态规划
目前我只能想到用二维DP去做，和“1035 不相交的线”的代码一模一样，当然在力扣上提交之后，时间和内存均只打败了5%

二维DP的含义：dp[i][j] 以第 i 个字母为结尾的 t 的子串，和以第 j 个字母为结尾的 s 的子串，其最长公共子序列的长度，和前几题的定义一致，本题也不要求连续。

这份代码是错的！递推公式里存在认识误区，没有取min操作

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
       
        n = len(s)
        m = len(t)
        if m < n :
            return False
        dp = [[0]*(n+1) for _ in range(m+1)]

        for i in range(1,m+1):
            for j in range(1,n+1):
                if t[i-1] == s[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 dp[m][n]==n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

动态规划的方法学习一下代码随想录的解答。

下面理解的是错的，不等式是不一定成立的，我的代码能通过可能只是运气

需要学习的是，本题规定，s 为 t 的子串，所以当两者元素不相等时，不需要向前面的题目一样去做 max 处理，因为如果对 s 的index进行减法操作，值是一定会变小的。即 dp[i][j-1] <= dp[i-1][j] 。

还是按照代码随想录的思路来理解，只能对字符串 t 进行删除操作

注意意义，第一个下标代表 t 的子串，第二个下标代表 s 的子串。该操作，只减去 t 的下标，就等价于字符串中的“删除”操作！

代码随想录的思路是：只能对字符串 t 进行删除操作，不能对字符串 s 进行删除操作，所以只能是， dp[i][j] = dp[i-1][j] 。

对自己的代码修改：

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
       
        n = len(s)
        m = len(t)
        if m < n :
            return False
        dp = [[0]*(n+1) for _ in range(m+1)]

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

        return dp[m][n]==n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

通过自己对本题的理解，以及自己的代码和代码随想录的代码，的两次实验，本题对遍历顺序没有要求，不管是先遍历 t , 后遍历 s ，还是先遍历 s ，后遍历 t 均可。

一点理解

如果是不要求连续的，和子序列有关的题，二维DP数组的含义就是，前 i 个字符，和前 j 个字符，其中满足条件的最大值，这种情况下，子序列的开头为0，结尾为当前 index，但是结尾元素不一定满足二者相等。如果是要求连续的，和子串有关的题，二维DP数组的含义就是，以第 i 个字符结尾的连续子串，和以以 j 个字符结尾的连续子串，其中满足条件的最大值，这种情况下，子串的开头不详，结尾为当前 index，结尾元素一定满足二者相等，如果不相等就会被赋值为0 。

本题的进阶问题的解答

vector<vector<int> > dp(len2 , vector<int>(26, 0));

for (char c = 'a'; c <= 'z'; c++) {
    int nextPos = -1; //表示接下来再不会出现该字符

    for (int i = len2 - 1; i>= 0; i--) {  //为了获得下一个字符的位置，要从后往前
        dp[i][c - 'a'] = nextPos;
        if (t[i] == c)
            nextPos = i;
    }
}
1
2
3
4
5
6
7
8
9
10
11

		int index = 0;
		for (char c : s) {
			index = dp[index][c - 'a'];
			if (index == -1)
				return false;
		}
		return true;

1
2
3
4
5
6
7
8

class Solution {
public:
	bool isSubsequence(string s, string t) {
		t.insert(t.begin(), ' ');
		int len1 = s.size(), len2 = t.size();
		
		vector<vector<int> > dp(len2 , vector<int>(26, 0));

		for (char c = 'a'; c <= 'z'; c++) {
			int nextPos = -1; //表示接下来再不会出现该字符

			for (int i = len2 - 1; i>= 0; i--) {  //为了获得下一个字符的位置，要从后往前
				dp[i][c - 'a'] = nextPos;
				if (t[i] == c)
					nextPos = i;
			}
		}

		int index = 0;
		for (char c : s) {
			index = dp[index][c - 'a'];
			if (index == -1)
				return false;
		}
		return true;

	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Python实现：

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # 防止bug:s的第一个元素即为t的第一个元素的情况
        t = ' ' + t
        # dp = [[0] * 26] * len(t) 这种方式初始化的二维列表不可取
        # dp表示每个位置上26个字符下一次出现在t中的位置, 不再出现用-1表示
        dp = [[0 for i in range(26)] for i in range(len(t))]
        for j in range(0, 26):
            nextPos = -1
            for i in range(len(t)-1, -1, -1):
                dp[i][j] = nextPos
                if(t[i] == chr(ord('a') + j)):
                    nextPos = i

        index = 0
        for x in s:
            index = dp[index][ord(x) - ord('a')]
            if(index == -1):
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

代码随想录的代码

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        dp = [[0] * (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]
        if dp[-1][-1] == len(s):
            return True
        return False
1
2
3
4
5
6
7
8
9
10
11
12

我的代码(当天晚上理解后自己编写)

115 不同的子序列

未看解答自己编写的青春版

这题和之前的题的感觉就不一样了，不会，没有思路。因为有可能"rarararat" 和 “rat”，或者"ratrarararat" 和 “rat” ，这些情况都很困惑我。

题意解读

本题表面上，是求解，给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。换句话说，有多少种对 s 字符串删除元素的方式，使字符串 s 变成字符串 t 。

重点

二维DP的含义：dp[i][j] 以第 i 个字母为结尾的 s 的子串，和以第 j 个字母为结尾的 t 的子串，出现 t 的个数。

本题的递推公式很难想，难就难在，要想到，如果当前匹配的两个值相等，那么总的匹配数等于“用当前字符匹配”+“不用当前字符匹配”。

就按照代码随想录中的讲解去理解，index减一，就相当于删除的操作

因为不需要对 t 进行删除操作，所以不需要在其相对应的维数上做减一。一定要想清楚上面的逻辑。

想清楚上面的点之后，初始值的设定也是一个坑，要注意哪种情况下赋值为1。

本题可以使用一维滚动数组，因为不同时需要 [i-1][j] 和 [i][j-1]

一维数组的写法，后面复习可以考虑，一刷先掌握二维。

这题还挺难的，不多做记录，要多刷

放上代码随想录题解的链接。
不同的子序列

代码随想录的代码

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]
        for i in range(len(s)):
            dp[i][0] = 1
        for j in range(1, len(t)):
            dp[0][j] = 0
        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[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

一维数组的方法：

class SolutionDP2:
    """
    既然dp[i]只用到dp[i - 1]的状态，
    我们可以通过缓存dp[i - 1]的状态来对dp进行压缩，
    减少空间复杂度。
    （原理等同同于滚动数组）
    """
    
    def numDistinct(self, s: str, t: str) -> int:
        n1, n2 = len(s), len(t)
        if n1 < n2:
            return 0

        dp = [0 for _ in range(n2 + 1)]
        dp[0] = 1

        for i in range(1, n1 + 1):
            # 必须深拷贝
            # 不然prev[i]和dp[i]是同一个地址的引用
            prev = dp.copy()
            # 剪枝，保证s的长度大于等于t
            # 因为对于任意i，i > n1, dp[i] = 0
            # 没必要跟新状态。 
            end = i if i < n2 else n2
            for j in range(1, end + 1):
                if s[i - 1] == t[j - 1]:
                    dp[j] = prev[j - 1] + prev[j]
                else:
                    dp[j] = prev[j]
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

学习了学习了，一维数组的方法，用深拷贝，copy()方法，这样就不用去考虑遍历顺序了。

前面有道题，也是用一维数组，为了不对历史值覆盖，用的倒序遍历，如果拷贝一下，就不需要倒序遍历了。

经过如上方法的启发，前面有几道题，也可以使用一维数组了！

N刷的时候，可以去写写！不知道我不copy，倒序去写，行不行？

我的代码(当天晚上理解后自己编写)

583 两个字符串的删除操作

未看解答自己编写的青春版

弄懂了上一题，这道题就改改代码就好了，然后再注意一下，初始化。我第一次遍提交的时候，就是初始化那里想错了。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)
        if n == 0:
            return m
        if m==0 :
            return n

        dp = [[0] * (n+1) for _ in range(m+1)]
     
        for i in range(m+1):
            dp[i][0] = i
        for j in range(n+1):
            dp[0][j] = j
       


        for i in range(1, m+1):
            for j in range(1, n+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],dp[i][j-1])+1
        return dp[m][n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

这道题用不了一维数组。

重点

看了代码随想录的题解，这题其实和1143.最长公共子序列基本相同，只要求出两个字符串的最长公共子序列长度即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

有点意思，没想到。
C++的代码

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));
        for (int i=1; i<=word1.size(); i++){
            for (int j=1; j<=word2.size(); j++){
                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 word1.size()+word2.size()-dp[word1.size()][word2.size()]*2;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

代码随想录的代码

和上题类似的删除字符串的动态规划版本

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0] * (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, dp[i-1][j] + 1, dp[i][j-1] + 1)
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我的代码(当天晚上理解后自己编写)

72 编辑距离

未看解答自己编写的青春版

难，思路没转过去。以为根据题意，操作word1 , 使其与 word2 相等，以为在递推关系中，不需要考虑 index 代表 word2 的那一维，太天真！因为操作不仅有删除，还有插入和替换，那么如果现在两者的 index 的元素不相等了：(下面第一维代表word1 , 第二维代表word2)

dp[i-1][j]+1 ：代表对word1进行一次删除操作。
dp[i][j-1]+1 ：代表对word1进行一次插入操作，插入word2中下标为 j 的元素
dp[i-1][j-1]+1：代表对word1进行一次替换操作，将word1[i]替换为word2[j]

重点

就是递推关系。

下面第一维代表word1 , 第二维代表word2

dp[i-1][j]+1 ：代表对word1进行一次删除操作。
dp[i][j-1]+1 ：代表对word1进行一次插入操作，插入word2中下标为 j 的元素
dp[i-1][j-1]+1：代表对word1进行一次替换操作，将word1[i]替换为word2[j]

编辑距离

此题需要N刷

代码随想录的代码

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        dp = [[0] * (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], dp[i-1][j], dp[i][j-1]) + 1
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

我的代码(当天晚上理解后自己编写)

动态规划之编辑距离总结篇

动态规划之编辑距离总结篇

回文串系列，必须要多刷，这种动态规划的思路，是我不可能想到的

回文串系列的难点在于如何利用回文串的特性

所以要用二维DP数组，来判断 [ i , j ] 是否为回文串。同时，因为DP数组的定义， j 一定是大于 i 的，所以在遍历时， j 是从 i 开始遍历的，更进一步的，必须先遍历 i ，再遍历 j ，因为 j 是由 i 控制的，当然这个逻辑很简单的，下意识的就会先遍历 i ，再遍历 j 。

647 回文子串

未看解答自己编写的青春版

动态规划，虽然有一些坑，但是都Debug解决掉了，不足的是：在运行时间上只打败了5%，又是一个耗时的垃圾算法。

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        if n <= 1:
            return n

        dp = [0]*n
        dp[0] = 1


        for i in range(1,n):
            temp = 0
            end = i      
            while i > 0 :  
                temp += self.judge(s[i-1:end+1])
                i -= 1
            # 前面 i 已经发生变化了，这里要用之前存的end值
            dp[end] = 1 + dp[end-1] + temp
        print(dp)
        
        return dp[n-1]


    def judge(self,s):
        if s == '' :
            return 0

        n = len(s)
        left = 0
        right = n-1
        while left < right :
            if s[left]==s[right]:
                left+=1
                right-=1
            else :
                return 0

        return 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

dp数组的含义就是，前 i 个字符中，回文串的数量，当加入一个新字母时，新字母自己肯定是一个，然后就是从新字母开始，不断地向前兼容字符，每次多兼容一个，比如 ：‘avcd’+‘d’ ，就是依次去计算 ‘dd’ ‘cdd’ ‘vcdd’ ‘avcdd’ 是否是回文串，要用一个while循环去计算。

再有一个容易坑的地方，就是我在循环中对 i 操作了，后面赋值的时候，要用之前储存好的值。其实稍微改一下可能更容易理解。

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        if n <= 1:
            return n

        dp = [0]*n
        dp[0] = 1


        for i in range(1,n):
            temp = 0
            start = i      
            while start > 0 :  
                temp += self.judge(s[start-1:i+1])
                start -= 1
            # 前面 i 已经发生变化了，这里要用之前存的end值
            dp[i] = 1 + dp[i-1] + temp
        print(dp)
        
        return dp[n-1]


    def judge(self,s):
        if s == '' :
            return 0

        n = len(s)
        left = 0
        right = n-1
        while left < right :
            if s[left]==s[right]:
                left+=1
                right-=1
            else :
                return 0

        return 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

看看，代码随想录有没有什么，加速的操作，学习一下。

重点

厉害了！和我的思路完全不一样！不管是动态规划还是双指针法，学习了！

定义二阶的DP数组，dp[i][j[，代表 [ i , j ] 这个区间内的子串，是不是回文串，如果是，那么左右两边各加入一个字符时，如果两个字符相同，那么新字符串明显就是回文串，快速判断！

回文子串

代码随想录的解答，比我的解答，少了每次都去判断一个长度为 s 的回文子串的过程，我的复杂度是O(n3)，代码随想录的解答都是O(n2)。

我自己写的本质上是垃圾暴力，要学习随想录的解法！

本题是第一道，从下到上，从左到右，进行遍历的题！

代码随想录的代码

动态规划：

class Solution:
    def countSubstrings(self, s: str) -> int:
        dp = [[False] * len(s) for _ in range(len(s))]
        result = 0
        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: #情况一 和 情况二
                        result += 1
                        dp[i][j] = True
                    elif dp[i+1][j-1]: #情况三
                        result += 1
                        dp[i][j] = True
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14

动态规划：简洁版
这个版本没什么意思，就是把判断都合并了而已，并不是加了什么剪枝操作，代码逻辑也不清晰，不学习。

class Solution:
    def countSubstrings(self, s: str) -> int:
        dp = [[False] * len(s) for _ in range(len(s))]
        result = 0
        for i in range(len(s)-1, -1, -1): #注意遍历顺序
            for j in range(i, len(s)):
                if s[i] == s[j] and (j - i <= 1 or dp[i+1][j-1]): 
                    result += 1
                    dp[i][j] = True
        return result
1
2
3
4
5
6
7
8
9
10

双指针法：

class Solution:
    def countSubstrings(self, s: str) -> int:
        result = 0
        for i in range(len(s)):
            result += self.extend(s, i, i, len(s)) #以i为中心
            result += self.extend(s, i, i+1, len(s)) #以i和i+1为中心
        return result
    
    def extend(self, s, i, j, n):
        res = 0
        while i >= 0 and j < n and s[i] == s[j]:
            i -= 1
            j += 1
            res += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

我的代码(当天晚上理解后自己编写)

516 最长回文子序列

未看解答自己编写的青春版

不会。

重点

看了解答，根本原因还是自己没有理解细致，上面那一题的思路！

最长回文子序列

本题的初始化是很难想到的一个点！注意注意！

本题的初始化部分，很值得学习

代码随想录的代码

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp = [[0] * 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][-1]
1
2
3
4
5
6
7
8
9
10
11
12

我的代码(当天晚上理解后自己编写)

写到现在，才发现，动态规划的遍历顺序，是由递推关系的推导方向决定的。

这一版的动态规划的题目，一刷完感觉没有完全理解，好像还有一点朦胧的地方，主要是编辑距离的系列题目。

所有的困惑，目前都集中在，对dp数组的设定上。再进一步就是，dp数组的定义与递推公式的关系，如果想的简单一点，就是正确的，按照代码思想录的解答完全讲的通，但是我再深入想一步，就似乎总感觉不对，尤其是，当我想模拟dp数组时。

解决办法

二刷时，对DP数组进行打印！切记切记

动态规划最强总结篇

动态规划最强总结篇

动态规划已完结，下面开始复习环节。