leetcode 常规dp问题通解思路_leetcode dp

---

基本上所有的递归都能转化为dp。递归给出一个近似于人的想法思路。计算时候从结尾往前走，在写代码的时候不要考虑是怎么完成的。而dp是从前往后走，每次dp都依赖于前面的dp，所以每个dp存储当前位置的最优值。

---

斐波那契数列 经典开篇

1. 爬楼梯 lc 70

一次只能上一阶，或者两阶。n个台阶几种走法。

（1）递归

class Solution:
    def climbStairs(self,n):
        if n==1:
            return 1
        if n==2:
            return 2
        return self.climbStairs(n-1)+self.climbStairs(n-2)
1
2
3
4
5
6
7

• 后面好多题目都是从这个题目变化过来的，当前的走法变成了分一步和两步的和,像二叉树一样分下去，并且给出了递归的出口。
• 递归的正向思路，反向求解。基本所有递归和dp的问题没有序列先后的关系，所以正向走完全可以，即下面dp的求解。

（2）dp

class Solution:
    def climbStairs(self, n):
        if n == 1:
            return 1
        if n == 2:
            return 2
        dp = [0 for _ in range(n + 1)]
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12

• 可以按照递归写出来再反推回dp节省计算复杂度。考虑dp存储的是每个位置需要的步数。而且dp只依赖于前两个，无需从头再次完全遍历（整数拆分），即思考好转移公式。

2. 强盗抢劫 lc 198

题目描述：抢劫一排住户，但是不能抢邻近的住户，求最大抢劫量。[1,2,3,1] ，偷窃到的最高金额 = 1 + 3 = 4 。

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:return 0
        if len(nums) == 1:return nums[0]
        if len(nums) == 2:return max(nums)
        res = [0]*len(nums)
        res[0]=nums[0]
        res[1]=max(nums[1], nums[0])

        for i in range(2,len(nums)):
            res[i] = max(res[i-1],res[i-2]+nums[i])
        return res[-1]
1
2
3
4
5
6
7
8
9
10
11
12

• dp存放当前位置能偷取的最大值。
• 每次都去找要当前+前两位和前一位的max。
• 无穷种路径，dp是常规解法。把问题的难度一下降低了。

3. 强盗在环形街区抢劫 lc 213

上一题是一个单list。本题目是list的首尾要重合。

class Solution:
    def rob_(self, nums: List[int]) -> int:
        res = [0]*len(nums)
        res[0]=nums[0]
        res[1]=max(nums[1], nums[0])

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

    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:return 0
        if len(nums) == 1:return nums[0]
        if len(nums) == 2:return max(nums)
        res1 = self.rob_(nums[0:-1])
        res2 = self.rob_(nums[1::])
        return max(res1,res2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 环形特点很难思考，劈开改变问题为两条袋子分开，正好拼成一个环。
• 有很多公共代码，很难维护，这个问题代码风格值得学习。

最长递增子序列

通向公式需要每次都从最优里面再次遍历一遍。

1. 最长递增子序列 leetcode 300

本题目是这个系列的基础
（1）dp存放的是当前位置的最大值，是里层循环每一个位置+1的值遍历取max。

class Solution:
	def lengthOfLIS(int[] nums):
	    dp=[1]*len(nums)
	    for i in range(1,len(nums)):
	        for j in range(i):
	            if nums[i]>nums[j]:
	            	#最后一个位置比当前大，说明当前应该有多1个的子序列
	                dp[i]=max(dp[i],dp[j]+1)
	    return max(dp)
1
2
3
4
5
6
7
8
9

• 所有的数都是无顺的，所以每个位置都放当前最长的结果。需要列举几个实例[3,2,7,4]。
• 这就表明为啥最的问题很显著用dp，因为虽然问题错综复杂，但是最一定是满足一个相同的套路，而且每次都被拆解开。所谓的最优子问题和重复的解法。
• 很多不是最的要看能不能把问题拆分成相同的操作。
• ==无需尽善尽美，因为还是遍历了每个位置，没有找到一个点可以不必在从头遍历，因为整个数据是无序的，如果不好找这样的点，就都遍历一遍。==整个逻辑和程序可以运行起来，和滑窗字符串一样。

2. 一组整数对能够构成的最长链 leetcode 646

与300题一样

class Solution:
	def findLongestChain(nums):
	    nums = sorted(nums, key=lambda x: x[1])
	    dp = [1]*len(nums)
	    for i in range(1,len(nums)):
	        for j in range(i):
	            if nums[j][1]<nums[i][0]:
	                dp[i]=max(dp[i],dp[j]+1)
	    return max(dp)
1
2
3
4
5
6
7
8
9

3. 最长摆动子序列 leetcode 376

解法一：
本题和回溯问题中海水流向题都需要问题解耦，一个基本子模块只完成一个任务，有多个任务时候需要上多个子模块。
（1）. 常规想法，用两个dp数组，遍历序列上扬和下降，与300题目不同的是，如果当前是上扬的，需要在所有下降里找到最大，如果当前是下降的则在所有上扬数组找最大。
（2）.既然是找当前的最大，那就是dp，实现正常dp的思路即可。

class Solution(object):
    def wiggleMaxLength(self, nums):
    	inc, dec = [1] * len(nums), [1] * len(nums)
    	for i in range(len(nums)):
    		for j in range(i):
    			if nums[i] > nums[j]:
    				inc[i] = max(inc[i],dec[j]+1)
    			elif nums[i] < nums[j]:
    				dec[i] = max(dec[i],inc[j]+1)
    	return max(dec[-1],inc[-1])
1
2
3
4
5
6
7
8
9
10

• 上面的抢劫最大值是和值本身有关，所以要dp和nums的加和，这里求最长最短，dp和nums本身没关系，只需要比较大小即可。
  解法二：
  仍然用两个dp，但是发现类似交叉的感觉，如果是上升则应该是在当前下降的位置+1上升的位置平移，下降是上升的地方+1下降部分平移。这个思路没有继承前面的一致性思路，可以忽略这种解法。

class Solution(object):
    def wiggleMaxLength(self, nums):
        """
      [0, 1,2, 3, 4, 5, 6,7, 8,9]
输入: [1,17,5,10,13,15,10,5,16,8]
inc   [1, 2,2, 4，4，4,4,4, 6,6]
dec   [1, 1,3, 3，3，3,5,5，5,7]
      [1, 2,3, 4, 4, 4,5,5, 6,7]
        """
        n = len(nums)
        if n <= 1:
            return n
        inc, dec = [1] * n, [1] * n
        for x in range(1, n):
            if nums[x] > nums[x - 1]:
                inc[x] = dec[x - 1] + 1
                dec[x] = dec[x - 1]
            elif nums[x] < nums[x - 1]:
                dec[x] = inc[x - 1] + 1
                inc[x] = inc[x - 1]
            else:
                inc[x] = inc[x - 1]
                dec[x] = dec[x - 1]
        return max(inc[-1], dec[-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

4.乘积最大子数组 lc 152

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        max_dp = copy.deepcopy(nums)
        min_dp = copy.deepcopy(nums)

        for i in range(1,len(nums)):
            max_dp[i] = max(max_dp[i],nums[i]*max_dp[i-1],nums[i]*min_dp[i-1])
            min_dp[i] = min(min_dp[i],nums[i]*max_dp[i-1],nums[i]*min_dp[i-1])
        return max(max(max_dp),max(min_dp))
        
        # [2,6,-2,4]
        # [2,3,-12,-48]
        max_dp = [float('-inf')] *len(nums)
        min_dp = [float('inf')] *len(nums)

        max_dp[0] = nums[0]
        min_dp[0] = nums[0]

        for i in range(1,len(nums)):
            max_dp[i] = max(nums[i],nums[i]*max_dp[i-1],nums[i]*min_dp[i-1])
            min_dp[i] = min(nums[i],nums[i]*max_dp[i-1],nums[i]*min_dp[i-1])
        
        return max(max(max_dp),max(min_dp)) 
  
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转移方程的一致性。
• 和最长摆动有点类似，因为正负号会引起摆动，因此没办法用一个dp来解决问题，所以用两个dp，一个记录最大值，一个记录最小值。因为最小值乘以一个负数会成为最大值。
• 问题是连续的乘积max，所以要是能连续住一定只需要看前一个和本位置的乘积即可，因为乘一个int其abs只会增大不会减少，不能连续住就从自己开始一个新的篇章。（补充：统计机器学习的乘积会把前面所有的信息都带过来）
• 重点在max的三项，所有dp都会面临这个问题，把自己放上来就会使得如果都不合适的话，从自己开始另起一个新篇章。

5.最大子序和 lc 53

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

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

• 每个dp位置记录当前位置的求和到此的最大值。
• 如果前一个小于0没必要加了，就是当前位置，否则当前数加上前一个dp位置。

俄罗斯套娃

class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes.sort(key = lambda x:(x[0],-x[1]))
        length = len(envelopes)
        dp =[1]*length

        for i in range(length):
            for j in range(i):
                if envelopes[i][1]>envelopes[j][1]:
                    dp[i]=max(dp[i],dp[j]+1)
        return max(dp)
1
2
3
4
5
6
7
8
9
10
11

• 先排序好第一个之后，第二个就是最长子序列的问题。
• 最长子序列把问题拆解到最小，每次只能操作一个，循环起来完成了所有。

分割整数

1. 分割整数的最大乘积 leetcode 343

题目描述：For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

（1）.最大还是想到dp，其次，既然是编程实现，则要考虑如何实现遍历和搜索，所有数字分割的都是逐个拆，与 两数求和题目 一样如下的遍历。
（2）.利用300题目的经典搜索思路，很容易思考到mem[i] = max(mem[i],j*mem[i-j])，但是结果不对，大方向又没问题，思考后原因是因为j * mem[i - j]，这个至少是三项相乘，因为mem[i-j]至少是两项相乘，所以要补充一个两项相乘j * (i-j)。

class Solution:
    def integerBreak(self, n):
        if n == 1:
            return 1
        mem = [-1 for i in range(n + 1)]
        mem[1] = 1
        for i in range(2, n + 1):
            for j in range(1, i):
            #与递归不同是从前往后走，把前面的都记录下来
                mem[i] = max(mem[i], j*(i - j), j*mem[i - j])
        return mem[-1]
1
2
3
4
5
6
7
8
9
10
11

递归写法

class Solution:
    def integerBreak(self, n):
        if n == 1:
            return 1

        result = -1
        for i in range(1, n):
        	#注意这里和dp的不同，这里是固定了n，找所有i的可能性的最大值
            result = max(result, i*(n - i), i * self.integerBreak(n - i))

        return result
1
2
3
4
5
6
7
8
9
10
11

补充一个思路，乘积最大应该是拆分的几个数差异最相近，初中的几个平均数的概念，利用这个编程也是AC的，但是为了思路的一致性，不写上来了。

• 上面这两个写法特别有代表性，思路一样，dp利用存储特点节省了大量的计算次数，递归给出计算的思路，dp从前往后计算并且存储当前的最优值便于后面使用所以循环也都是如此。

补充两数求和：

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

class Solution(object):
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            num = target - nums[i]
            if num in nums[i+1:]:
                return [i, nums.index(num,i+1)]
1
2
3
4
5
6

（1）.没有思路的时候想计算机要利用搜索的方式完成任务。

2. 按平方数来分割整数 leetcode 279

题目描述：For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。与343不同的是，本题目只需要找到所有最小的分割，不存在343的乘积会有遗漏的问题。

class Solution(object):
    def numSquares(self, n):
        output = [float('inf')] * (n + 1)
        output[0] = 0
        output[1] = 1
        for i in range(2, n + 1):
            j = 1
            while (j * j <= i):
            #与爬楼梯类似，发现了一个合理点i-j**2,则应该在此+1，爬楼梯是dp[n]=dp[n-1]+dp[n-2],表示用一步上还是两步上
                output[i] = min(output[i], output[i - j * j] + 1)
                j = j + 1

        return output[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13

3. 分割整数构成字母字符串 leetcode 91

题目描述：Given encoded message “12”, it could be decoded as “AB” (1 2) or> “L” (12)

通向只依赖前两个，不需要从头再次遍历。

• 递归，因为递归的写法即是整个思路的流程，比较容易理解，递归去除第一位和前两位，总的结果为：每次分支的和。递归返回的结果return值是解码的个数。
• 如果s[0]和s[0:2]都合法，那么f(s[:])=f(s[1:])+f(s[2:]) ==>爬楼梯，斐波那契数列
• 如果s[0]合法而s[0:2]不合法的话，那么f(s[:])=f(s[1:])
• 如s[0]都不合法，那么不可能存在编码，没有继续的分支

这个博客写的很好

class Solution:
    def numDecodings(self, s):
        if not s:
            return 0
        return self._numDecodings(s)
        
    def _numDecodings(self, nums):
    	#一路拆解，如果为空了，那就说明找到了1种解法
        if not nums:
            return 1
		#返回一个求和的数，所以定义在这
        result = 0
        #也可以是num[0]!=0，不等于0即1~9再无其他
        if 1 <= int(nums[0]) <= 9:
            result += self._numDecodings(nums[1:])
        
        if len(nums) >= 2 and 10 <= int(nums[0:2]) <= 26:
            result += self._numDecodings(nums[2:])
        return result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

注意：
（1）程序进入时候如果是空串返回0种解码；
（2）在递归函数里，使用两个并列的if对一个result求和，这个逻辑非常重要，蕴含了上述伪代码的所有情况，两个是if是并列依次执行的，不满足则跳过，这样的双if在树bfs建树和bfs遍历树也是这样使用。所以逻辑不好写的时候想想双if，而且逻辑的解耦，比如本题目只做了加法应该的情况。
（3）在递归里面如果nums为空了，说明分解完了，即找到了，return应该是1。一个case是10，进入了第二个if，分解之后nums是空，其实是找到了，应该return1，但是对于输入的纯空串又矛盾，所以建立（1）。
（4）不一定是所有都是if xxx：return。比如这个直接设置初值，进入不了if的就return初始值。

2. dp

class Solution:
    def numDecodings(self, s):
        # dp[i] = dp[i-1](if s[i] is vaild)+dp[i-2](id s[i-2:i] is vaild)
        # dp[1]-->dp[-1]
        #s    1 2 3 4 5 0
        #dp 1 1
        if not s or s[0] == '0':
            return 0
        dp = [0]*(len(s)+1)
        #dp[0] = 1 if s[0]!='0' else 0
        #dp[1] = 1 if s[0]!='0' else 0
        dp[0]=dp[1]=1
        
        for i in range(2,len(s)+1):
            if s[i-1] != '0':
                dp[i] = dp[i-1]
            if '10'<=s[i-2:i]<='26':
                dp[i] += dp[i-2]
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

（1）递归的思路是f(s[:])=f(s[1:])+f(s[2:])，dp的思路是f(i)=f(i-1)(where s[i] valid)+f(i-2)(where s[i-1:i+1] valid) i>=2 ，正好是反着来，整个条件和写法都是倒着来，但是为了凑出f(1)=f(0)+f(-1)的这个-1需要多往后凑一个，初学的时候总是会正反觉得都可以，确实如此，和顺序无关，因此dp和递归才能转化。不过这个dp不需要如300题形成图，每次都从头扫描过来，只需要扫描前两个，看通项公式。所以只需要手动把最初始的case解决就可以了。
（2）上面的描述体现了dp的两个重点，通项公式，初始化。

矩阵路径

1. 矩阵的最小路径和 lc 64

    [[1,3,1],
     [1,5,1],
     [4,2,1]]
     只能向下或者向右走。
    Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum.
1
2
3
4
5

（1）.递归思路很自然,接近人的思路
先给一个比较通用的方法，以后类似的代码都是这样的解，用一个变量保存要返回的值，而不是下面的递归都在return眼花缭乱。

import numpy as np
class Solution():
    def minPathSum(self, arr):
        arr = np.array(arr)
        return self._minimum_path_sum(arr, 0, 0)

    def _minimum_path_sum(self, arr, i, j):
        # 与双if类似，需要考虑if的顺序，本题需要优先考虑是结尾就立马停下来
        if i == arr.shape[0] - 1 and j == arr.shape[1] - 1:
            return int(arr[i][j])
        elif i == arr.shape[0] - 1:
            res = arr[i][j] + self._minimum_path_sum(arr, i, j + 1)
        elif j == arr.shape[1] - 1:
            res = arr[i][j] + self._minimum_path_sum(arr, i + 1, j)
        else:
            right = self._minimum_path_sum(arr, i, j + 1)
            down = self._minimum_path_sum(arr, i + 1, j)
            res = arr[i][j] + min(right, down)
        return int(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 该方法是每次找到一个新地方，从和这个位置开始，往下去找下去。等效于下面的代码。

import numpy as np
class Solution():
    def minPathSum(self, arr):
        arr = np.array(arr)
        return self._minimum_path_sum(arr, 0, 0)

    def _minimum_path_sum(self, arr, i, j):
        # 与双if类似，需要考虑if的顺序，本题需要优先考虑是结尾就立马停下来
        res = 0
        if i == arr.shape[0] - 1 and j == arr.shape[1] - 1:
            return int(arr[i][j])
        elif i == arr.shape[0] - 1:
            tmp = arr[i][j] + self._minimum_path_sum(arr, i, j + 1)
            res += tmp
        elif j == arr.shape[1] - 1:
            tmp = arr[i][j] + self._minimum_path_sum(arr, i + 1, j)
            res += tmp
        else:
            right = self._minimum_path_sum(arr, i, j + 1)
            down = self._minimum_path_sum(arr, i + 1, j)
            tmp = arr[i][j] + min(right, down)
            res += tmp
        return int(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

个人不是很喜欢的方式递归：

class Solution():
    def minimum_path_sum(self,arr):
    	arr = np.array(arr)
       return self._minimum_path_sum(arr, 0, 0)

    def _minimum_path_sum(self,arr,i,j):
    #与双if类似，需要考虑if的顺序，本题需要优先考虑是结尾就立马停下来
        if i==arr.shape[0]-1 and j==arr.shape[1]-1:
            return int(arr[i][j])
        elif i==arr.shape[0]-1:
            return arr[i][j]+self._minimum_path_sum(arr,i,j+1)
        elif j==arr.shape[1]-1:
            return arr[i][j]+self._minimum_path_sum(arr,i+1,j)
        right = self._minimum_path_sum(arr,i,j+1)
        down = self._minimum_path_sum(arr,i+1,j)
        return int(arr[i][j]+min(right,down))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 也用到了再封装一次函数的思路，如果有条件冲突或者需要再次输入必须值的case下就再次封装一次函数。
• 先想清楚这个递归要return的是值，所以每次都是当前arr[i][j]加的过程。
• 属于搜索问题，每次进入递归时候要先标记当前的位置已经走过，因为这个是求值，所以要加起来。

（2）.dp解法：

import numpy as np
class Solution:
	def dp_minimum_path_sum(A):
	A = np.array(A)
    dp=np.zeros_like(A)
    dp[0][0]=A[0][0]
	#如果在最上行和最左边只有一种走法
    for i in range(A.shape[0]):
        dp[i][0] = A[i][0]+dp[i-1][0]
    for j in range(A.shape[1]):
        dp[0][j] = A[0][j] + dp[0][j-1]

    for i in range(1,A.shape[0]):
        for j in range(1,A.shape[1]):
            dp[i][j] = A[i][j] + min(dp[i-1][j],dp[i][j-1])
    return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 矩阵的总路径数 lc 62

题目描述：统计从矩阵左上角到右下角的路径总数，每次只能向右或者向下移动。

（1）.递归

def count_path_sum(A,x,y):
    if A.shape[0] == 1 and A.shape[1]==1:
        return 1
    if x==A.shape[0]-1:
        return 1
    if y==A.shape[1]-1:
        return 1
    return count_path_sum(A,x+1,y)+count_path_sum(A,x,y+1)
1
2
3
4
5
6
7
8

• 与64不同的是仅仅计数有几种走法，而不是走几次。所以第一行和第一列都只有一种走法就是一条道走下去，别无他法。
• 最后还是要求所有的可能性，所以还是求和。

（2）.dp

import numpy as np
class Solution:
	def dp_count_path_sum(A):
	    dp = np.zeros_like(A)
	    dp[:,0]=1
	    dp[0,:]=1
	    for i in range(1,A.shape[0]):
	        for j in range(1,A.shape[1]):
	            dp[i][j]=dp[i-1][j]+dp[i][j-1]
	    return int(dp[-1][-1])
1
2
3
4
5
6
7
8
9
10

数组区间

1. 数组区间和 lc 303

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3

class NumArray:
    def __init__(self, nums: List[int]):
        self.num_sum = [0,]
        for i in range(len(nums)):
            self.num_sum.append(self.num_sum[i]+nums[i])

    def sumRange(self, i: int, j: int) -> int:
        return self.num_sum[j+1] - self.num_sum[i]
1
2
3
4
5
6
7
8

• 非常好的写法，工程里也常用这样的写法，初始化的时候就把该计算的计算好了，如pytorch的dataset里加载和预处理。dp的思路体现在初始化里，而且初值设置的也很好。

2. 数组中等差递增子区间的个数 lc 413

A = [0, 1, 2, 3, 4]

return: 6, for 3 arithmetic slices in A:

[0, 1, 2], [1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3, 4], [ 1, 2, 3, 4], [2, 3, 4]

思路很容易想到能不能用到前面的结论，如果前面是等差数列，下一个数也满足条件则dp+1 。
直接找等差序列是连续的，所以不必每次从头再遍历一遍，只需要就近的通向。如果只有[1,2,3,4]1,2,3是等差，3的位置dp=1,4的位置dp[i]=dp[i-1]+1 = 2，意思是有1，2,3,4和2,3,4，最终结果为1+2 = 3

class Solution:
	    def numberOfArithmeticSlices(self, A):
        n = len(A)
        if n < 3:
            return 0
        dp = [0] * n
        for i in range(2, n):
            if A[i] - A[i - 1] == A[i - 1] - A[i - 2]:
                dp[i] = dp[i - 1] + 1
        return sum(dp)
1
2
3
4
5
6
7
8
9
10

最长公共子串、子序列问题

这个博客内容不错

1.最长公共子序列 lc 1143

（1）递归方法

class Solution:
	def longestCommonSubsequence(text1,text2):
	    if text1 == '' or text2 == '':
	        return 0
	    if text1[-1]==text2[-1]:
	        return 1+longestCommonSubsequence(text1[:-1],text2[:-1])
	    else:
	        a_less = longestCommonSubsequence(text1[:-1], text2)
	        b_less = longestCommonSubsequence(text1, text2[:-1])
	        return max(a_less,b_less)

#第二种传递参数的方法
	def CLS2(str1,str2):
	    def CLS2_(i,j):
	        maxval=0
	        if i == -1 or j == -1:
	            return 0
	
	        if str1[i] == str2[j]:
	            return CLS2_(i-1,j-1)+1
	        else:
	        	return max(CLS2_(i-1,j),CLS2_(i,j-1))
	    return CLS2_(len(str1) - 1, len(str2) - 1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 递归的方法和人的思维类似，先看最后一位如果相等，排除最后一位，return的结果是最长的长度+1，最后一位如果不相等，则分别去除1,2的最后一位，这是递归的soul。

（2）dp方法

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        l = [[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]:
                    l[i][j] = l[i-1][j-1] + 1
                else:
                    l[i][j] = max(l[i-1][j], l[i][j-1])
        return l[-1][-1]
1
2
3
4
5
6
7
8
9
10
11

• dp存储每个位置以该字母结尾的最长长度。
• 递归的逆过程，先初始化第一行第一列为0，转移方程是，如果最后一个相等，去对角线找，如果不相等，去找上面各去除一位的值。

2.最长公共子串列 lc

（1）.循环实现

class Solution:
    def CLS2(str1, str2):
        maxlen = 0
        str1len = len(str1)
        str2len = len(str2)

        for i in range(str1len):
            for j in range(str2len):
                len_ = 0
                while i + len_ < str1len and j + len_ < str2len and \
                        str1[i + len_] == str2[j + len_]:
                    len_ += 1
                maxlen = max(len_, maxlen)
        return maxlen
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 这个题目注意循环遍历的方法，注意这个是需要三重循环，第一二个循环是基本套路，会把所有的字符都遍历，容易想到。第三个循环是关键，不容易想到，在每个都遍历到的基础上去计数。
• 思路比较简单好想，就是模板匹配，见另一个专题滑窗。dp和递归从后往前一般是为了减到0，其实前后没有顺序的关系。
• 补充一个重要内容：所有的字符串包括滑窗问题都是一样的，字符串的重要约束是：必须有自己的顺序，因此才能一个一个按照首字母的方式丢弃。

（2）dp实现

def LCstring(string1,string2):
    len1 = len(string1)
    len2 = len(string2)
    res = [[0 for i in range(len1+1)] for j in range(len2+1)]
    result = 0
    for i in range(1,len2+1):
        for j in range(1,len1+1):
            if string2[i-1] == string1[j-1]:
                res[i][j] = res[i-1][j-1]+1
                result = max(result,res[i][j])  
    return result
print(LCstring("helloworld","loop"))
1
2
3
4
5
6
7
8
9
10
11
12

（3）递归实现（不成功，但是值得分析）

def CLS2(str1,str2):
    def CLS2_(i,j):
        maxval=0
        if i == -1 or j == -1:
            return 0

        if str1[i] == str2[j]:
            val = CLS2_(i-1,j-1)+1
            maxval = max(maxval,val)
        else:
            return 0
            CLS2_(i - 1, j)
            CLS2_(i, j - 1)
        return maxval
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 找了好多都没找到递归的实现，我们分析一下，情况是，如果有一个串为空则return 0说明不可能有相同的部分。
• 如果最后一个位置相等，去除它，并且结果+1.
• 如果不相等，那前面的递归就要停下来，与此同时要进入新的递归，各自去除一位。问题来了，这个不是一个最小子过程，是两个过程，先停下来置为0，然后再进去，但是return了后面的代码不可达了，与最长子序列不同的是有两个动作
• 那为何我这么执着的一定要去写递归？因为有说法递归都能转化为dp，那dp是否也都应该能转化为递归那？等我和众神们讨论有结果show出来。

军神提出来的版本，是不是网上首个递归方法的求解

class Solution:
    def CLS2(self,str1,str2):
        self.maxval = 0
        visited = {}
        def CLS2_(i,j):
            val = 0
            if (i, j) not in visited:
                if i == -1 or j == -1:
                    return 0
                #军神提出了这点，包含了所有所有情况，如果该位相等，要看前一位是不是也相等，对这个问题进一步的分类讨论
                if str1[i] == str2[j]:
                    if str1[i-1] == str2[j-1]:
                        val = CLS2_(i-1,j-1)+1
                    else:
          #这里不是直接return，而是复制val，因为本方法返回的是val
                        val = 1
                    self.maxval = max(self.maxval, val)
                CLS2_(i - 1, j)
                CLS2_(i, j - 1)
                visited[(i,j)]=val
                return val
            else:
                return visited[(i,j)]
        CLS2_(len(str1) - 1, len(str2) - 1)
        return self.maxval
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

• 关键点是军哥对该问题进行了进一步的分类讨论，与遍历方式第三个while循环一样，如果当下的方式解决不了，试着再进一步的分类讨论。
• 递归的整个框架不能变，必须是能化成子问题进入，如果进入时候要分情况不是简单的进入需要在上面的if地方去做修改，整个思路又很流畅，符合题目意思。而且if else只能进入一个，如果连续就求和，不连续就只有一个。
• 关键的事情再说一遍：结合上面的不正确的解，原因在于改变了递归进入的内容，必须要移动它，保持整个框架。

背包问题

上面的子序列求解两个字符串关系，以及下面的最大正方形和下面的背包问题都是两个维度的dp。

背包原理分析
背包原理分析
墙裂推荐这个视频，非常好

0.原理分析与代码实现

一个旅行者有一个最多能装M公斤的背包，现在有n件物品，他们的重量分别是W₁，W₂…W_n ,他们的价值分别是C₁,C₂,…C_n。求旅行者得到的最大价值。

• 分析：一个背包，容量有限，要求装的东西价值最大，而且装法很多，拿与不拿很混乱，很显然可以用dp解决。 涉及到的约束很多：背包容量，物品重量，物品价值，背包的最大价值。建立一个能融合在一起的dp，这种混乱的问题都思考是否有后向无效原则即：当前的取值只与前一次取值有关，不必要再往前思考。

• dp做一个二维表，行表示当前所拿到的物品，列为当前的容量。

• 第一行和第一列都为0表示0个物品价值为0,0个空间没法拿东西，价值为0。

• 由当前包空间是否放得下当前物品，可以有如下表和转移公式：

• 
  

（1）01背包（物品只有一个）

class Soultion:
	def __init__(self,n,v,c):
		self.things_weight= n#list
		self.values = v#list
		self.capacity = c#num
		
	def knapsack01(self):
		dp=[[0 for _ in range(self.capacity)] for _ in range(len(self.things_weight))]
		#外层循环是物品
		for i in range(len(self.things_weight)):
		#内层循环是背包容量
			for j in range(self.capacity):
				if self.things_weight[i] > j:
					dp[i][j] = dp[i-1][j]
				else:
				#分成拿与不拿，看哪个情况下的值大
					dp[i][j] = max(dp[i][j-self.num_things[i]]+self.values[i],dp[i][j-1])
		return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（2）优化存储空间，因为后无效性。只需要一维向量存储就可以。如下图，去了i仅仅保留j。滚动数组。

class Soultion:
	def __init__(self,n,v,c):
		self.things_weight = n#list
		self.values = v#list
		self.capacity = c#num
		
	def knapsack01(self):
		dp = [0 for _ in range(self.capacity)]
		for i in range(len(self.things_weight)):
		#这是重点！！！必须从后往前循环,没有if直接判断谁大谁小直接上结果
			for j in range(self.capacity,0,-1):
				dp[j] = max(dp[j],dp[j-self.things_weight[i]]+self.values[i])
1
2
3
4
5
6
7
8
9
10
11
12

• 外循环即要把所有的物品都遍历一遍。
• 注意一定要从后往前循环，否则会覆盖前面的值。

（2）完全背包，东西有无限个（01背包物品只有一个只有拿和不拿）

class Soultion:
	def __init__(self,n,v,c):
		self.things_weight= n#list
		self.values = v#list
		self.capacity = c#num
		
	def knapsack01(self):
		dp=[[0 for _ in range(self.capacity)] for _ in range(len(self.things_weight))]
		#外层循环是物品
		for i in range(len(self.things_weight)):
		#内层循环是背包容量
			for j in range(self.capacity):
				if self.things_weight[i] > j:
					dp[i][j] = dp[i-1][j]
				else:
					for k in range(j//self.things_weight[i]):
					#分成拿与不拿，看哪个情况下的值大
						dp[i][j] = max(dp[i][j-k*self.num_things[i]]+k*self.values[i],dp[i][j-1])
		return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在01背包优化的基础上再次优化一下。

class Soultion:
	def __init__(self,n,v,c):
		self.things_weight = n#list
		self.values = v#list
		self.capacity = c#num
		
	def knapsack01(self):
		dp = [0 for _ in range(self.capacity)]
		for i in range(len(self.things_weight)):
		#这是重点！！！必须从后往前循环
			for j in range(self.capacity,0,-1):
				if j>self.things_weight[i]:
					for k in range(j//self.things_weight[i]):
						dp[j] = max(dp[j],dp[j-k*self.things_weight[i]]+k*self.values[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14

再次优化：

• 完全背包如上图，也是拿或者不拿，拿了一个，剩下的取前一次本行的，因为本行的那个对应位置代表了该位置能无限拿的价值。
• 这次的优化是对比优化，也是把i去了，但是去了之后发现循环的方向变了。

class Soultion:
	def __init__(self,n,v,c):
		self.things_weight = n#list
		self.values = v#list
		self.capacity = c#num
		
	def knapsack01(self):
		dp = [0 for _ in range(self.capacity)]
		for i in range(len(self.things_weight)):
		#这是重点！！！必须从前往后遍历，时刻改变本行的值
			for j in range(self.things_weight[i],self.capacity):
				dp[j] = max(dp[j],dp[j-self.things_weight[i]]+self.values[i])
1
2
3
4
5
6
7
8
9
10
11
12

（3）多重背包（物品有限个）

有N种物品和容量为V的背包，第i件物品最多有n[i]个，每个物品重量和价值一直，求将哪些放进来总价值最大。
问题分析：
01背包只能放1个，完全背包能放无限个，多充背包放有限个。

先从01背包开始优化。每个物品有s[i]个

class Soultion:
	def __init__(self,n,v,c,s):
		self.things_weight = n#list
		self.values = v#list
		self.capacity = c#num
		self.single_counts = s
		
	def knapsack01(self):
		dp = [0 for _ in range(self.capacity)]
		for i in range(len(self.things_weight)):
		#这是重点！！！必须从后往前循环
			for j in range(self.capacity,0,-1):
				k =0
				#与完全背包的差异
				while (k>=self.single_counts[i] and k*self.things_weight[i]<=j):
					k+=1
					dp[j] = max(dp[j],dp[j-k*self.things_weight[i]]+k*self.values[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 所有背包都是从01背包过来，这个与完全背包不一样的是要再次约束物品数量。

1. 划分数组为和相等的两部分 lc 416

Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

（1）回溯法

class Solution:
	def canPartition_(self, nums):
    """
    :type nums: List[int]
    :rtype: bool
    """
    nums_sum=sum(nums)
    if nums_sum%2!=0:
        return False
    else:
        nums_sum//=2
    rec=[False]
    def search(nums,i,s=0):
        if i==len(nums) or s>nums_sum:
            return
        if nums[i]+s==nums_sum:
            rec[0]=True
            return
        else:
            search(nums,i+1,s)
            search(nums,i+1,s+nums[i])
    search(nums,0,0)
    return rec[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 是回溯的基本题目。去搜索看是否能满足需求。
• 框架是：选择当前这位和不选择当前这位开辟两个分支去寻找，在内部的计算时候都是加上当前的这位。问题的解耦。

（2）.dp背包

class Solution:
	def canPartition(nums):
	    nums_sum=sum(nums)
	    if nums_sum%2!=0:
	        return False
	    else:
	        nums_sum//=2
	    dp = [False]*(nums_sum+1)
	    dp[0] = True
	    #背包问题之所以和物品顺序无关要先遍历物品再遍历空间
	    for i in nums:
	        for j in range(nums_sum,i+1,-1):
	            dp[j] = dp[j] or dp[j-i]
	    return dp[nums_sum+1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2. 改变一组数的正负号使得它们的和为一给定数字 lc 494

一个数组改变符号，和为目标结果。
Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5
Explanation:

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.

class Solution:
	def findTargetSumWays(nums, S):
	    def helper(index, acc):
	        if index == len(nums):
	            #注意，必须是走到底才能判断说是对还是不对
	            if acc == S:
	                return 1
	            else:
	                return 0
	        return helper(index + 1, acc + nums[index]) + helper(index + 1, acc - nums[index])
	    return helper(0, 0)
1
2
3
4
5
6
7
8
9
10
11

• 所有数相加相不相等，有几种组合都是dfs搜索方式。
• 递归都是开辟了几个通路，是否加在一起是看结果要啥。
• 这个题目说明了递归和回溯的不同，回溯有不对的要回退的，有些值可以不选，但是这个题目所有值必须选。只能用递归一点点的走，和树一样，都遍历到。
  （2）dp

在这里插入代码片
1

3. 01 字符构成最多的字符串 lc 474

Input: Array = {“10”, “0001”, “111001”, “1”, “0”}, m = 5, n = 3 Output: 4

Explanation: There are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10”,“0001”,“1”,“0”

在这里插入代码片
1

01 字符构成最多的字符串 lc 474

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
Input: Array = {“10”, “0001”, “111001”, “1”, “0”}, m = 5, n = 3
Output: 4
Explanation: There are totally 4 strings can be formed by the using of
5 0s and 3 1s, which are “10”,“0001”,“1”,“0”

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        #构建矩阵的方式，与numpy反着来，numpy直接输入(len(strs),n,m),这里正好先定义最里层即numpy的[-1]的值，接着依次反向定义。
    	#最里层循环最快,之后调用最里面在最外面
        dp = [[[0] *(n+1) for _ in range(m+1)] for _ in range(len(strs) + 1)]
        for i in range(1, len(strs) + 1):
            ones = strs[i-1].count("1")
            zeros = strs[i-1].count("0")
            for j in range(m+1):
                for k in range(n+1):
                #反着操作，不行就用numpy更直接
                    dp[i][j][k] = dp[i-1][j][k]
                    if j >= zeros and k >= ones:
                        dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-zeros][k - ones] + 1)
        return dp[-1][-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 这个题目难点在于现在是三维的dp01背包。
• 定义矩阵的list时候，和遍历使用时候顺序正好相反，因为嵌套的顺序决定。
• 难点1：升级为三维dp时候之前的二维背包的初始化背包容量为0和物品为0变成第一个矩阵全零。代表了第一次背包为0和所有的物品都为0的情况。
• 难点2：每一个新字符串都顺次继承之前的结果，同时遍历两种情况，因为每个位置要同时把字符串放进去。
• 框架没变，最外层循环是循环物品，看要不要拿，里层才是对值的判断。

优化一下，因为其实不需要k这个概念，只依靠上一个

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        if len(strs) == 0:
            return 0
        dp = [[0] * (n+1) for _ in range(m+1)]
        for strs_item in strs:
            zeros = strs_item.count("0")
            ones = strs_item.count("1")
            #注意这里是倒着来的，因为是01背包
            for i in range(m, zeros - 1, -1):
                for j in range(n, ones - 1, -1):
                    dp[i][j] = max(dp[i][j], 1+dp[i- zeros][j-ones])
        return dp[m][n]

作者：LeahChao
链接：https://leetcode-cn.com/problems/ones-and-zeroes/solution/bei-bao-wen-ti-zhuan-hua-zhu-bu-kong-jian-you-hua-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4. 找零钱的最少硬币数 lc 322

题目描述：给一些面额的硬币，要求用这些硬币来组成给定面额的钱数，并且使得硬币数量最少。硬币可以重复使用。
物品：硬币
物品大小：面额
物品价值：数量
Example 1:
coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1)

Example 2: coins = [2], amount = 3 return -1.

class Solution:
    def coinChange(self,coins, amount):
        dp=[float('inf') for _ in range(amount+1)]
        dp[0] = 0
        for i in range(len(coins)):
            for j in range(coins[i],amount+1):
                dp[j] = min(dp[j],dp[j-coins[i]]+1)
        return dp[-1] if dp[-1] != float('inf') else -1		
1
2
3
4
5
6
7
8

• 非常明显是个典型的完全背包的题目。

5. 找零钱的硬币数组合

class Solution:
    def change(self,amount,coins):
        if len(coins) == 0 and amount==0:
            return 1
        elif len(coins) == 0 and amount!=0:
            return 0
        dp = [0]*(amount+1)
        dp[0] = 1
        for coin in coins:
            for j in range(coin,amount+1):
            #类似斐波那契，有合适的就拆出来
                dp[j]+=dp[j-coin]
        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13

回溯解法：

class Solution:
    def change(self,amount, coins):
        def dfs(start_index, amount, coins,res):
            if amount == 0:
                res[0]+=1
                return
            if amount<0:
                return
            for i in range(start_index,len(coins)):
                dfs(i,amount-coins[i],coins,res)
        res = [0]
        start_index = 0
        dfs(start_index, amount, coins, res)
        return res[0]

	#如果变动index则是每个元素只能取一次
	def solution_wrong(self, amount, coins):
        ans = [0]
        def backtrack(coins, index, amount, ans):
            if amount == 0:
                ans[0] += 1
                return
            if amount < 0:
                return
            for i in range(index, len(coins)):
                backtrack(coins, index+1, amount - coins[i], ans)
        backtrack(coins, 0, amount, ans)
        return ans[0]
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

• 为了保持回溯代码的完整性，继续使用了index，但是没使用。
• 这个回溯和一般的回溯不一样的是一个值能无限取用。是一个标准的回溯问题。见后面回溯篇章专门有可以重复取和不重复取的讨论。
• 递归return什么： 如果返回的结果的值是通过几个递归加起来的结果，如一共的路径和，则可以定义一个val，return他们的求和。如果题目是把所有路径只要对就算一个，则没法定义一个变量去求和，应该定义一个外部的变量，把所有的情况累积在这里。

6. 字符串按单词列表分割 lc 139

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

说明：

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

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。

输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回
true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
注意你可以重复使用字典中的单词。

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

参考这个博客内容

class Solution:
    def wordBreak(self, s, wordDict):
        return self._wordBreak(s, set(wordDict), 0)

    def _wordBreak(self, s, words, start):
        if start == len(s):
            return True

        for i in range(start + 1, len(s) + 1):
            sub = s[start:i]
            if sub in words and self._wordBreak(s, words, i):
                return True

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

• 标准的字符串问题的回溯解法。
• 想到一个字母一个字母加入，判断是否在字典中的想法很自然。
• 字符串遍历的通用方法，在滑动窗口这个篇幅也是这么做。

回溯，一致性思路解法：

class Solution:
    '''
    之前的想法是顺序思考，不断增长字符串，反向思考，不断去除列表中字符串长度，
    直到正好长度为0
    '''

    def _wordBreak(self, s, words, index):
        if 0 == len(s):
            self.ans[0] = True
            return
        for i in range(index,len(words)):
            if s.startswith(words[i]):
                self._wordBreak(s[len(words[i]):], words, index)

    def wordBreak(self, s, wordDict):
        self.ans = [False]
        self._wordBreak(s, wordDict, 0)
        return self.ans[0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 很值得关注的一个问题是：回溯到底回的是什么。对比前一个题目找硬币，回溯的是硬币，本题目中回溯的是字符串的长度，如果没走通要退回来。

（2）dp
仔细想还真是背包的问题。我们遍历到第一个"aaaa"，此时我们要知道f(7)是否成立，我们只需要知道f(3)是否可以成立即可，如果f(3)成立，我们这个时候只需要将"aaaa"放入即可。而我们需要知道f(3)是否可以成立，我们就需要直到f(-1)能否成立，但是-1超出了边界，所以我们判断"aaa"能否放入，也就是我们判断f(0)能否成立即可。而我们直到对于空字符串来说，直到我们单词字典中不选出单词即可，所以f(0)=True。所以按照这个过程，我们可以很快写出下面的代码。
而且是有序背包的话则要求后遍历物品，与一般背包不同。

class Solution:
    def wordBreak(self, s, wordDict):
        len_s = len(s)
        mem = [False]*(len_s+1)
        mem[0] = True
        for i in range(1, len_s + 1):
            for word in wordDict:
                if i >= len(word) and mem[i - len(word)] \
                	and word == s[i-len(word):i]:
                    mem[i] = True
        return mem[-1]
1
2
3
4
5
6
7
8
9
10
11

• 把每个位置的情况都看一下是否合理。

---

以下是几个特殊的dp问题

---

正方形的最大遍历

属于比较特殊的dp，dp内存储以该点为左下角的正方形的最长边的边数，dp的转移方程为dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1。即考虑该点为上面点由最薄弱的部分决定。

求最大正方形面积 lc 221

matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]
只由0,1构成，求由1构成的正方形的最大面积
1
2
3
4
5
6
7

class Solution:
    def maximalSquare(self,matrix):
        dp = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
        maxvec = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == '1':
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
                    maxvec = max(dp[i][j],maxvec)
        return maxvec**2
1
2
3
4
5
6
7
8
9
10
11
12
13

• 注意传入的matrix是list[list[str]]，所以不能像np.array一样索引，所以要如上述代码一样操作产生dp，双for如上去遍历

正方形的最大边数 lc 1277

matrix =
[
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]
]

dp=
[
[0,1,1,1],
[1,1,2,2],
[0,1,2,3]
]
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def countSquare(self,matrix):
        dp = [[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
        count = 0
        for i in range(matrix):
            for j in range(matrix[i]):
                if matrix[i][j] == 1:
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
                count += dp[i][j]
        return count
1
2
3
4
5
6
7
8
9
10
11
12
13

股票

字符串

1. 删除两个字符串的字符使它们相等 lc 583

删除最少的字符，让两个串相同。

（1）.递归

class Solution:
    def minDistance(self, word1: str, word2: str) -> int: 
        n1, n2 = len(word1), len(word2)
        
		def dfs(i,j):
			if i == n1:
	#如果第一个串走到尽头，则剩下第二个串剩余的部分为最后的剩余长度
				return n2-j
			if j == n2:
				return n1-i
			res = float('inf')
			if word1[i] == word2[j]:
				res = min(res,dfs(i+1,j+1))
			else:
				res = min(res,1+min(dfs(i+1,j),dfs(i,j+1))
			return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 思路比较自然，return是一个值，最短的删除字符个数。如果相同则往下一个走，如果不一样递归去遍历看看是删除哪个比较好。注意，在递归值的时候，不是return，是赋值，最后的最后return。

（2）dp
思路是找到删除最短的字符个数，那之前的最长序列是相同的，用补集的思路不就ok了吗。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int: 
        n1 = len(word1)
        n2 = len(word2)
        if n1 == 0:
            return n2
        if n2 == 0:
            return n1
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        for i in range(n1 + 1):
            for j in range(n2 + 1):
                if i == 0 or j == 0:
                    continue
                elif 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])
        # print(dp[-1][-1])
        max_num = dp[-1][-1]
        return (n1 + n2)- 2 * max_num
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.最小编辑距离 lc 72

插入，删除，替换，使之变成一样的。（这个中英文都能使用，要中文要重新定义一下，这个题目做nlp的必须会，不会就要背下来。
）

class Solution:
    def minDistance(self, word1, word2):
        n1, n2 = len(word1), len(word2)
        # 初始化 dp 数组
        dp = [[0]*(n2+1) for _ in range(n1+1)]
        for i in range(n1+1):            # 第 0 列
            dp[i][0] = i
        for j in range(n2+1):            # 第 0 行
            dp[0][j] = j
        # 更新 dp 数组
        for i in range(1, n1+1):
            for j in range(1, n2+1):
            #先用字符判断，而后更改dp
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
        return dp[n1][n2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数。

• 当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

• 其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。

复制粘贴

def divPrime(num):
    lt = []
    while num != 1:
        for i in range(2, int(num + 1)):
            if num % i == 0:  # i是num的一个质因数
                lt.append(i)
                num = num / i  # 将num除以i，剩下的部分继续分解
                break
    return sum(lt)
1
2
3
4
5
6
7
8
9

• 这个题目转换为求质数分解的和，回顾一下质数分解的方法，即遍历一下，因为都是从头开始的，如果有合数自然被质数分解来了。
• dp写法

3最长回文串

class Solution:
    def isPalinedrome(self,s,l,r):
        while l<r:
            if s[l] != s[r]:
                return False
            l+=1
            r-=1
        return True

    def longestPalindrome(self, s: str) -> str:
        length = len(s)
        if length==0:
            return ''
        best=''
        for i in range(length):
            for j in range(i+1,length):
                if j-i+1>len(best) and self.isPalinedrome(s,i,j):
                    best = s[i:j+1]
        if best=='':
            return s[0]
        return best


class Solution:
    def longestPalindrome(self, s: str) -> str:
        # s[i]==s[j] --> dp[i][j] = dp[i+1][j-1] 这样写就不会越界，让j在外面，i在里面，本来就不分先后
        if not s:
            return ''
        length = len(s)
        # dp = [[False]*length]*length
        dp = [[False for _ in range(length)] for _ in range(length)]
        max_length = 1
        start_index = 0
        for i in range(length):
            dp[i][i] = True

        # ababa
        for j in range(1, length):
            for i in range(j):
                if s[i] == s[j]:
                    if j - i + 1 < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]
                if dp[i][j]:
                    if max_length < j - i + 1:
                        max_length = j - i + 1
                        start_index = i
        return s[start_index:max_length + start_index]

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
49
50

• dp的物理含义是从i到j就是dp[i][j]是否是回文，如果s[i]==s[j]相等，则只需要看他里面的是不是，如果是，则他也是，否则初始化的时候就是false，如果i与j的距离小于3在相等的情况下自然是true。
• 1，2，3，4，5，6，7，8
  2，6
  3，5

总结

1.递归和动态规划都是将原问题拆成多个子问题然后求解，先思考一下通项公式是什么，一般可以按照需要把前面都遍历一遍，只需要依靠前几个就可以，或者是都不是。
2.问题复杂可以按照递归先想出来思路，然后完全逆向的写dp。
3.双if的思路。
4.递归返回值。
5.max里带上自己本身可以从自己开始另开一个新篇章。