Leetcode分类练习-动态规划

动态规划

动态规划常常用于有重叠子问题和最优子结构性质的问题，动态规划方法所消耗时间往往远少于朴素解法。

---

主要思想
如果要解决一个给定问题，我们需要解其不同部分，即子问题，再根据子问题的解得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列，如果运用递归的方式来求解回重复计算很多相同的子问题，利用动态规划思想可以减少计算量。
动态规划仅仅解决每个子问题一次，具有天然剪枝的功能，从而减少计算量。
一旦某个给定子问题的解已经解出，则将其记忆化存储下来，便于下次需要同一个子问题解之时直接查表。

动态规划解题模版

• 确定动态规划状态
• 写出状态转移方程（画出状态转移表）
• 考虑初始化条件
• 考虑输出状态
• 考虑对时间、空间复杂度的优化（bonus）

例题详解

例题：最长上升子序列
题目描述
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例：

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

说明：

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

解题思路
第一步：确定动态规划状态

• 是否存在状态转移？
• 什么样的状态比较好转移，找到对求解问题最方便的状态转移？

想清楚到底是直接用需要求的，比如长度作为dp保存的变量还是用某个判断问题的状态，比如是否是回文子串来作为方便求解的状态。
该题目可以直接用一个一位数组dp来存储转移状态，dp[i]可以定义为以nums[i]这个数结尾的最长递增子序列长度。举个实际例子，比如在nums[10, 9, 2, 5, 3, 7, 101, 18]中，dp[0]表示数字10的最长递增子序列长度，那就是本身，所以为1，对于dp[5]对应的数字7来说的最长递增子序列是[2, 5, 7], 或者[2, 3, 7], 所以dp[5] = 3

第二部：写出一个好的状态转移方程

• 使用数学归纳法思维，写出准确的状态方程

比如还是刚刚那个nums数组，我们思考一下如何得到dp[5] = 3的， 既然是递增的子序列，我们只要找到nums[5], 也就是7，前面那些结尾比7小的子序列，然后把7接到最后，就可以形成一个新的递增子序列，这个新的子序列长度加1。当然可能会找到很多不同的子序列，比如刚刚上面列举的，但是只需要找到长度最长的作为dp[5]的值就行了。总结来说就是比较当前dp[i]的长度和dp[i]对应产生的新的子序列长度，我们用j来表示所有比i小的组数中的索引，可以用如下代码表示：

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

tips:在实际问题中，如果不能很快得出这个递推公式，可以先尝试一步一步把前面几步写出来，如果还是不行很可能就是dp数组的定义不够恰当，需要回到第一步重新定义dp数组的含义；或者可能是dp数组存储的信息还不够，不足以推出下一步的答案，需要把dp数组扩大为二维或者三维数组。

第三步：考虑初始条件
这是决定整个程序能否跑通的重要步骤，当我们确定好状态转移方程，我们就需要考虑一下边界值，边界值主要分为3个地方：

• dp数组整体的初始值；
• dp数组（二维）i=0和j=0的地方
• dp存放状态的长度，是整个数组的长度还是数组长度加1，这点需要特别注意。

对于本问题，子序列最少也是自己（当前的这个数），所以长度为1，这样我们就可以方便的把所有dp初始化为1，再考虑长度问题，由于dp[i]代表的是nums[i]的最长子序列长度，所以并不需要加1，所以代码表示就是dp = [1] * len*nums 。

这里额外总结几种python常用的初始化方法：

• 对于产生一个全为1，长度为n的数组：

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

• 对于产生一个全为0，长度为m，宽度为n的二维数组：

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

第四步：考虑输出状态
主要有以下三种形式，对于具体问题，我们一定要想清楚dp数组里存储的是哪些值，最后我们需要的是哪些值：

• 返回dp数组中最后一个值作为输出，一般对应二维dp问题
• 返回dp数组中最大的那个数字，一般对应记录最大值问题（该例题对应的就是这种情况）
• 返回保存的最大值，一般是Maxval = max(Maxval, dp[i])这样的形式

tips： 这个公式是在满足递增的条件下，也就是 nums[i] > nums[j] 的时候才成立，并不是nums[i]前面所有数字都满足这歌条件的，理解好这个条件就容易懂接下来在输出时候应该是max(dp)而不是dp[-1]，原因就是dp数组由于计算递增的子序列长度，所以dp数组里中间可能有值会是比最后遍历的数值大的情况，每次遍历nums[j]所对应的位置都是比nums[i]小的那个数。举个例子，比如nums = [1, 3, 6, 7, 9, 4, 10, 5, 6], 而最后dp = [1, 2, 3, 4, 5, 3, 6, 4, 5]。总结一下，最后的结果应该返回dp数组中最大的数。
最后加上考虑数组是否为空的判断条件，下面是解决该问题的完整代码：

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

第五步：考虑对时间、空间复杂度的优化（bonus)
切入点：我们看到，之前方法遍历dp列表需要$O(N)$，计算每个dp[i] 需要$O(N)$的时间，所以总的复杂度是$O(N^2)$。
前面遍历dp列表的时间复杂度肯定是无法降低，但是我们看后面在每轮遍历[0, i]的dp[i]元素的时间复杂度可以考虑设计状态定义，使得整个dp为一个排序俩表，这样我们自然想到了可以利用二分法把时间复杂度降到$O(NlogN)$.
这里可以进行尝试：

最长连续递增序列
题目描述
给定一个未经排序的整数数组，找到最长且连续的递增序列。

示例 1:
输入：[1, 3, 5, 4, 7]
输出：3
解释：最长连续递增序列是[1, 3, 5]，长度为3

解题思路
第一步：确定动态规划状态 对于这个问题，我们的状态dp[i]也是以nums[i]这个数结尾的最长递增子序列的长度

第二步：写出状态转移方程 这个问题，我们需要分两种情况考虑，第一种情况是如果遍历到的数nums[i]后面一个数不是比他大或者前一个数不是比他小，也就是所谓的不是连续的递增，那么这个数列最长连续递增序列就是他本身，也就是长度为1。 第二种情况就是如果满足有递增序列，就意味着当前状态只和前一个状态有关，dp[i]只需要在前一个状态基础上加一就能得到当前最长连续递增序列的长度。总结起来，状态的转移方程可以写成 dp[i]=dp[i-1]+1

第三步：考虑初始化条件 和上面最长子序列相似，这个题目的初始化状态就是一个一维的全为1的数组。

第四步：考虑输出状态 与上题相似，这个问题输出条件也是求dp数组中最大的数。

第五步：考虑是否可以优化 这个题目只需要一次遍历就能求出连续的序列，所以在时间上已经没有可以优化的余地了，空间上来看的话也是一维数组，并没有优化余地。

综上所述，可以很容易得到最后的代码：

def findLengthOfLCIS(self, nums:list[int]) -> int:
	if not nums: return 0
	dp = [1] * len(nums)
	for i in range(1, len(nums)):
		if nums[i] > nums[i-1]:
			dp[i] = dp[i-1]+1
		else:
			dp[i] = 1
	return max(dp)

总结: 通过这个题目和例题的比较，我们需要理清子序列和子数组（连续序列）的差别，前者明显比后者要复杂一点，因为前者是不连续的序列，后者是连续的序列，从复杂度来看也很清楚能看到即使穷举子序列也比穷举子数组要复杂很多。

承接上面的话题，我们接下来继续来看一个子序列问题，这次是另外一种涉及二维状态的题目。

题目描述
给定一个字符串s，找到s中最长的回文子串，你可以假设s的最大长度为1000

示例1:
输入：“babad”
输出：“bab”
注意："aba"也是一个有效的答案。

• 第一步：确定动态规划状态
  与上面两题不同的是，这歌题目必须用二维的dp数组来记录状态，主要原因就是子串有会问的限制。用两个指针来记录子串的位置可以很好的实现子串的回文要求，又因为最后结果需要返回的是子串，这里不同于之前题目的用dp保存长度，我们必须找到具体哪个部分符合回文子串的要求。这里我们定义dp[i][j]表示子串从s到j是否为回文子串。
• 第二步：写出状态转移方程
  当字符串首尾两个字符相等时，如果子串是回文，整体是回文，这里运用了动态规划的思想，相反，如果子串不是回文，那么整体肯定不是。对于字符串s，s[i,j]的子串是s[i+1, j-1], 如果子串只有本身或者空串，那肯定是回文子串了，所以我们讨论的状态转移方程，当其子串元素个数小于1时是不成立的，也就是 $(j-1)-(i+1)+1<2$的情况（整理得j-i<3)。所以当s[i] == s[j] 并且j-1<3 时，我们可以直接得出dp[i][j] 是True.
  综上所述得到状态转移方程：

if s[i] == s[j] :
	if j - i < 3:
		dp[i][j] = True
	else:
		dp[i][j] = dp[i+1][j-1]

• 第三步：考虑初始化条件
  我们需要建立一个二维的初始状态是false的来保存状态的数组来表示dp，又因为考虑只有一个字符的时候肯定是回文串，所以dp[i][i]肯定是True。

• 第四步：考虑输出状态
  这里dp表示的是从i到j是否是回文子串，这样一来就告诉我们子串的起始位置和结束位置，但是由于我们需要找到最长的子串，所以我们优化一下可以只记录起始位置和当前长度。

def longestPalindrome(s):
    length = len(s)
    #初始化dp数组，最大长度，起始子串位置
    dp = [[False]* length for i in range(length)]
    max_len = 1
    start = 0
    if length < 2:
        return s
    for i in range(length):
        dp[i][i] = True
    for j in range(1, length):
        for i in range(j):
            #print(s[j], s[i])
            if s[i] == s[j]:
                if j - i < 3:
                    dp[i][j] = True
                else:
                    dp[i][j] = dp[i+1][j-1]
            if dp[i][j]:
                cur_len = j-i+1
                if cur_len >= max_len:
                    max_len = cur_len
                    start = i
    return s[start: start+max_len]

输出结果：

s = 'babad'
sub = longestPalindrome(s)
print(sub)
"aba"

这是一个二维dp的经典题目，需要注意的就是定义dp数组的状态是什么，这里不用长度作为dp值而用是否是回文子串这个状态来存储也是一个比较巧妙的方法。

编辑距离
给定两个单词word1和word2，计算出将word1转换为word2所使用的最少操作数。
题目描述

你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
示例1:
输入：word1 = “horse”, word2=“ros”
输出：3
解释：
horse -> rorse
rorse -> rose
rose -> ros

解题思路
第一步：确定动态规划状态
这个题目涉及到两个字符串，所以我们最先想到就是用两维数组来保存转移状态，定义dp[i][j]为字符串word1长度为i和字符串word2长度为j时，word1转化成word2所执行的最少操作次数的值。

第二步：写出状态转移方程
关于这个问题的状态转移方程其实很难想到，这里提供的一个方向就是试着举个例子，然后通过例子的变化记录每一步变化得到的最少次数，来找到删除，插入，替换操作的状态转移方程具体应该怎么写。 我们采用从末尾开始遍历word1和word2， 当word1[i]等于word2[j]时，说明两者完全一样，所以i和j指针可以任何操作都不做，用状态转移式子表示就是dp[i][j]=dp[i-1][j-1]，也就是前一个状态和当前状态是一样的。 当word1[i]和word2[j]不相等时，就需要对三个操作进行递归了，这里就需要仔细思考状态转移方程的写法了。 对于插入操作，当我们在word1中插入一个和word2一样的字符，那么word2就被匹配了，所以可以直接表示为dp[i][j-1]+1 对于删除操作，直接表示为dp[i-1][j]+1 对于替换操作，直接表示为dp[i-1][j-1]+1 所以状态转移方程可以写成min(dp[i][j-1]+1,dp[i-1][j]+1,dp[i-1][j-1]+1)​

第三步：考虑初始化条件
我们还是利用dp转移表法来找到状态转移的变化（读者可以自行画一张dp表，具体方法在求最长子序列中已经演示过了），这里我们用空字符串来额外加入到word1和word2中，这样的目的是方便记录每一步操作，例如如果其中一个是空字符串，那么另外一个字符至少的操作数都是1，就从1开始计数操作数，以后每一步都执行插入操作，也就是当i=0时，dp[0][j]=j,同理可得，如果另外一个是空字符串，则对当前字符串执行删除操作就可以了，也就是dp[i][0]=i​。

第四步：考虑输出状态
在转移表中我们可以看到，可以从左上角一直遍历到左下角的值，所以最终的编辑距离就是最后一个状态的值，对应的就是dp[-1][-1]​。

第五步：考虑对时间，空间复杂度的优化 和上题一样，这里由于dp[i][j]只和dp表中附近的三个状态（左边，右边和左上边）有关，所以同样可以进行压缩状态转移的空间存储，如果觉得有兴趣可以参考@Lyncien的解法,对于时间方面应该并没有可以优化的方法。

def minDistance(self, word1, word2):
        #m,n 表示两个字符串的长度
        m=len(word1) 
        n=len(word2)
        #构建二维数组来存储子问题
        dp=[[0 for _ in range(n+1)] for _ in range(m+1)]
        #考虑边界条件，第一行和第一列的条件
        for i in range(n+1):
            dp[0][i]=i  #对于第一行，每次操作都是前一次操作基础上增加一个单位的操作
        for j in range(m+1):
            dp[j][0]=j #对于第一列也一样，所以应该是1,2,3,4,5...
        for i in range(1,m+1):  #对其他情况进行填充
            for j in range(1,n+1):
                if word1[i-1]==word2[j-1]: #当最后一个字符相等的时候，就不会产生任何操作代价，所以与dp[i-1][j-1]一样
                    dp[i][j]=dp[i-1][j-1]
                else:
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 #分别对应删除，添加和替换操作
        return dp[-1][-1] #返回最终状态就是所求最小的编辑距离

打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
题目描述

给定一个代表每个房屋存放金额的的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例1:
输入：[1, 2, 3, 1]
输出： 4
解释：偷窃1号房屋（金额=1），然后偷窃3号房屋（金额=3）。偷窃到的最高金额=1+3=4

解题思路
第一步：确定动态规划状态
直接定义题目所求的偷窃的最高金额，所以dp[i]表示偷窃第i号房子能得到的最高金额。

第二步：写出状态转移方程
如果我们不考虑限制条件相邻两个房子不能抢，那么问题就很简单。想得到第i个房间偷窃到的最高金额的时候，我们会考虑子问题前i-1​间的最高金额dp[i-1]，然后再加上当前房间的金额，所以最后可以表达为dp[i]=dp[i-1]+nums[i]。 需要注意的是，这里限制了相邻两个房子是不能抢的，接下来我们就要考虑两种情况。 如果抢了第i个房间，那么第i-1​肯定是不能抢的，这个时候需要再往前一间，用第i-2间的金额加上当前房间的金额，得到的状态转移方程是dp[i]=dp[i-2]+nums[i]。 如果没有抢第i​个房间，那么肯定抢了第i-1间的金额，所以直接有dp[i]=dp[i-1]。最后综合一下两种情况，就可以很快得到状态转移方程：dp[i]=max(dp[i-2]+nums[i],dp[i-1])​

第三步：考虑初始化条件
初始化条件需要考虑第一个房子和第二个房子，之后的房子都可以按照规律直接求解，当我们只有一个房子的时候，自然只抢那间房子，当有两间房的时候，就抢金额较大的那间。综合起来就是dp[0]=nums[0]，dp[1]=max(nums[0],nums[1])​。

第四步：考虑输出状态
直接返回状态转移数组的最后一个值就是所求的最大偷窃金额。

第五步：考虑对时间，空间复杂度的优化
间复杂度为$O(N)$不能再优化了，空间复杂度方面如果用动态规划是不能优化，但是如果用迭代的方法只存储临时变量来记录每一步计算结果，这样可以降到$O(1)$。

     def rob(self, nums):
     
        if(not nums):   #特殊情况处理
            return 0
        if len(nums)==1:
            return nums[0]
        n=len(nums)
        dp=[0]*n    #初始化状态转移数组
        dp[0]=nums[0]  #第一个边界值处理
        dp[1]=max(nums[0],nums[1])#第二个边界值处理
        for i in range(2,n):
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]) #状态转移方程
        return dp[-1]

解题思路

第一步：确定动态规划状态
直接定义题目所求的偷窃的最高金额，所以dp[i]表示偷窃第i号房子能得到的最高金额。

第二步：写出状态转移方程
和上个题目类似，这个题目不一样的是现在所有房屋都围成一个圈，相比于上个问题又增加了一个限制，这样一来第一个房子和最后一个房子只能选择其中一个偷窃了。所有我们把这个问题拆分成两个问题：
1.偷窃了第一个房子，此时对应的是nums[1:]，得到最大的金额value是v1。
2.偷窃了最后一个房子，此时对应的是nums:n-1，得到的最大金额value是v2。 最后的结果就是取这两种情况的最大值，即max(v1,v2)。
每个子问题就和上题是一样的了，所以可以直接得到状态转移方程还是dp[i]=max(dp[i-2]+nums[i],dp[i-1])

第三步：考虑初始化条件 初始化一个房子和两个房子的情况就是dp[0]=nums[0]，dp[1]=max(nums[0],nums[1])。

第四步：考虑输出状态 直接返回状态转移数组的最后一个值就是所求的最大偷窃金额。

第五步：考虑对时间，空间复杂度的优化
时间复杂度为$O(N)$不能再优化了，空间复杂度方面如果用动态规划是不能优化，但是如果用迭代的方法只存储临时变量来记录每一步计算结果，这样可以降到$O(1)$。

最后的代码实现：

def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        elif len(nums)<=2:
            return max(nums)
        def helper(nums):
            if len(nums)<=2:
                return max(nums)
            dp=[0]*len(nums)
            dp[0]=nums[0]
            dp[1]=max(nums[0],nums[1])
            for i in range(2,len(nums)):
                dp[i]=max(dp[i-1],dp[i-2]+nums[i])
            return dp[-1]
        return max(helper(nums[1:]),helper(nums[:-1]))

动态规划是算法中比较难的类型，但是其实主要是掌握一种思维，有了这种思维，其实很难的问题都能一步一步解决好。最后再推荐一些比较优质的动态规划文章。

掌握动态规划，助你成为优秀的算法工程师https://www.jiqizhixin.com/articles/2019-09-29-5

推荐MIT的动态规划练习资料，这份资料通过动态规划经典的问题让我们很清晰的了解到这个算法的魅力所在，对于新手入门动态规划是一个很不错的资料。Dynamic Programming Practice Problemshttps://people.cs.clemson.edu/~bcdean/dp_practice/

五分钟学算法的动态规划系列: 浅谈什么是动态规划以及相关的「股票」算法题 有了四步解题法模板，再也不害怕动态规划! （进阶版）有了四步解题法模板，再也不害怕动态规划！https://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485288&idx=1&sn=fd043fc723f38bcaecc90d9945981f8a&chksm=fa0e68e9cd79e1ffd965205bb06b1731539bf2e0bbc5991664f5d1d9721b346ec08c85bb9042&scene=21#wechat_redirect

主要参考的Leetcode 优秀题解： 动态规划设计方法&&纸牌游戏讲解二分解法 动态规划、Manacher 算法 编辑距离面试题详解 打家劫舍 II（动态规划，结构化思路，清晰题解）https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-she-ji-fang-fa-zhi-pai-you-xi-jia/

本文地址：https://blog.csdn.net/weixin_43959248/article/details/108110809