动态规划之数组长度加长规避初始化

文章目录

在动态规划算法中，当我们的递推公式出现i-1,i-2的时候，一般的做法肯定是对于len(nums)<1,或者<2的时候特判一下 所以我们就采用将dp数组开长一点这样，就不用理初始化的问题，但是要根据题目的意思，对于dp数组本身的值进行赋值为0，还是一个很小的数 nums数组的下标是不用变化的

例子1：打家劫舍

198.打家劫舍

打家劫舍的递推公式是 dp[i] = max(dp[i-1]+nums[i],dp[i-2]) 我们一般开的dp数组的长度是dp = [0]*len(nums),这样的话就会造成一些问题，就是当你的nums数组的长度小于3的时候，该公式使用不了,并且当你的数组的长度大于等于3的时候，前面的dp[0]和dp[1]的情况还需要特别判断

class Solution: def rob(self, nums: List[int]) -> int: # 可以使用记忆化搜索来做 # dfs(i) = max(dfs(i-1),dfs(i-2)+nums[i]) # 使用结果值作为返回值 n = len(nums) dp = [0]*(n) if n <3: return max(nums) else: dp[0],dp[1] = nums[0],max(nums[0],nums[1]) for i in range(2,n): dp[i] = max(dp[i-1],dp[i-2]+nums[i]) return dp[n-1]

那么我们应该如何改进？ 将dp = [0]*(len(nums)+2),也就是说，将dp数组的长度开长，将对应的递推公式修改一下，也就是dp数组部分的下标都保证不会出现负数dp[i+2] = max(dp[i+1],dp[i]+nums[i])

class Solution: def rob(self, nums: List[int]) -> int: # 可以使用记忆化搜索来做 # dfs(i) = max(dfs(i-1),dfs(i-2)+nums[i]) # 使用结果值作为返回值 n = len(nums) dp = [0]*(n+2) for i,c in enumerate(nums): # 原本是 dp[i] = max(dp[i-1],c+dp[i-2]),现在为了方便，dp方面每个都加上2 dp[i+2] = max(dp[i+1],c+dp[i]) return dp[-1]

例子2：最大子数组和

53.最大子数组和

这个递推公式是 dp[i] = max(dp[i-1]+nums[i],nums[i]),所以我们将dp数组开长一个，但是dp数组的初始值要赋值为一个很小的数，因为我们最后返回的是max(dp)

class Solution: def maxSubArray(self, nums: List[int]) -> int: # 定义dp[i]为以nums[i]结尾的最大连续子数组的和 # dp[i] = max(dp[i-1]+nums[i],nums[i]) n = len(nums) # 初始值设置为最小的值，这样后面返回max的时候才不会影响 dp = [-10**4]*(n) dp[0] = nums[0] for i in range(1,n): dp[i] = max(dp[i-1]+nums[i],nums[i]) return max(dp)