小白的动态规划学习

这是我在学习动态规划时，在力扣刷题的总结。参考了很多大佬的题解、总结。
包括但不限于：
动态规划系列
力扣加加动态规划
《算法笔记》
《LeetCode 101》

解题思考方法

• 确定dp数组（dp table）以及下标的含义
• 确定递推公式
• dp数组如何初始化
• 确定遍历顺序
• 举例推导dp数组

一维动态规划

509. 斐波那契数

• 初始值
• 看在不在备忘录里
• 递推公式
• 返回值

def fib(self, n):
memo={}
def dfs(n):
if n in memo:
return memo[n]
elif n<=1:
return n
else:
memo[n]=dfs(n-1)+dfs(n-2)
return memo[n]
return dfs(n)

70. 爬楼梯

其实就是斐波那契数列

每次能爬1层或2层，那么就是爬1层前的方法数，和爬2层前的方法数的和。

• dp初始化/+base值
• 递推，且返回dp

def climbStairs(self, n: int) -> int:
dp=[0]*(n+1)
def dfs(n):
if n==0:
return 1
elif n==1:
return 1
if dp[n]!=0:
return dp[n]
dp[n]=dfs(n-1)+dfs(n-2)
return dp[n]
return dfs(n)

413. 等差数列划分

def numberOfArithmeticSlices(self, nums: List[int]) -> int:
dp=[0]*len(nums)
for i in range(2,len(nums)):
if nums[i]-nums[i-1]==nums[i-1]-nums[i-2]:
dp[i]=dp[i-1]+1
return sum(dp)

198. 打家劫舍

本质也是斐波那契，只与前两个状态相关，可以简化存储

def rob(self, nums: List[int]) -> int:
pre1=pre2=0
for i in range(0,len(nums)):
cur=max(pre1,pre2+nums[i])
pre2=pre1
pre1=cur
return cur

213. 打家劫舍 II

根据限制条件：不能同时访问头和尾。则去头或去尾进行两次打劫，取大的那个。

def rob(self, nums: List[int]) -> int:
size=len(nums)
def rob(nums):
pre1=pre2=0
for i in range(len(nums)):
cur=max(pre1+nums[i],pre2)
pre1=pre2
pre2=cur
return cur
return max(rob(nums[1:]),rob(nums[:-1])) if size>1 else nums[0]

337. 打家劫舍 III

不再是线性结构

对当前节点有抢和不抢两种选择，抢就算上当前节点加上子树里不抢子树根节点的值；不抢就取左右子树里较大的值相加
后序遍历，得到左右子树中抢和不抢的结果

def rob(self, root: TreeNode) -> int:
def rob(root):
if not root:
return 0,0
left=rob(root.left)
right=rob(root.right)
v1=root.val+left[1]+right[1]
v2=max(left)+max(right)
return v1,v2
return max(rob(root))

二维

64. 最小路径和

每块最多能往下或往右走，那么就是最小和有两种选择方式

空间压缩：由于方向固定，且是最小路径和，往下走一层的话其实上一层就可以在计算后覆盖

def minPathSum(self, grid: List[List[int]]) -> int:
m=len(grid)
n=len(grid[0])
dp=[[0 for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
if i==0 and j==0:
dp[j]=grid[i][j]
elif i==0:
dp[j]=dp[j-1]+grid[i][j]
elif j==0:
dp[j]=dp[j]+grid[i][j]
else:
dp[j]=min(dp[j],dp[j-1])+grid[i][j]
return dp[-1]

221. 最大正方形

在上方补上一行，可以从1开始遍历
在当前数字为1的情况下，取左、上、左上的最小值，

def maximalSquare(self, matrix: List[List[str]]) -> int:
res = 0
m = len(matrix)
if m == 0:
return 0
n = len(matrix[0])
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 if matrix[i - 1][j - 1] == "1" else 0
res = max(res, dp[i][j])
return res ** 2

分割类

每次进行分割的时候有几种选择，每次选择后dp应该如何改变

91. 解码方法

在满足解码条件的时候可以按1个或2个划分13

def numDecodings(self, s: str) -> int:
n=len(s)
if n==0:
return 0
dp=[1,0]
dp[1]=1 if s[0]!='0' else 0
for i in range(1,n):
dp.append(0)
if s[i]!='0':
dp[-1]+=dp[-2]
if s[i-1:i+1]>='10' and s[i-1:i+1]<='26':
dp[-1]+=dp[-3]
dp.pop(0)
return dp[-1]

背包问题

1.分析是否为背包问题。
2.是三种背包问题（组合、TF、最值）中的哪一种。
3.是0-1背包问题还是完全背包问题。也就是题目给的nums数组中的元素是否可以重复使用。
4.如果是组合问题，是否需要考虑元素之间的顺序。需要考虑顺序有顺序的解法，不需要考虑顺序又有对应的解法

01背包

每个物品只能取一次，取或不取两种状态

• 定义dp维度和值的含义 一般i表示此时选择物品i，j表示容量为j，dp[i][j]为最大价值量
• 初始化 i=0 j=0时 有时还有i=1时，可以看for循环无法取到的就需要在初始化定义
• for循环
  • 循环物品
  • 循环容量(一般当前物品容量到目标容量倒序遍历)
    • dp是1维需要在j处逆序遍历
    • dp是2维正逆序都可以

完全背包

dp[i][w]为在前i个物品里选择，重量为w的最大价值数。与01背包不同在于每个物品都有无限个

对于物品i每次有拿或不拿两种状态

但是选择拿第i件物品后转移到dp[i][w-wt[i]]

与完全背包不同：

• 必须正向遍历
• 需考虑顺序决定i、j先后遍历顺序。

dp[i][w]=max(dp[i-1][w],dp[i][w-wt[i-1]]+v[i])

组合问题

公式：dp[i] += dp[i-num]

是否考虑顺序：

• 考虑顺序：先遍历容量，在遍历物品
• 不考虑顺序：先遍历物品，在遍历值

377. 组合总和 Ⅳ

完全背包

考虑顺序

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

494. 目标和

转换成求在使用前i个数字的情况下，填满j容量的背包最多有dp[i][j]种方法

S=left-right（left是加号总和，right是减号总和）

sum=left+right

def findTargetSumWays(self, nums: List[int], S: int) -> int:
#left-right=S sum=l+r l=(S+sum)//2 
if S>sum(nums):return 0
if (S+sum(nums))%2!=0:return 0
bigsize=(S+sum(nums))//2
dp=[0]*(bigsize+1)
dp[0]=1
for i in range(len(nums)):
for j in range(bigsize,nums[i]-1,-1):
dp[j]+=dp[j-nums[i]]#排列组合
return dp[-1]

518. 零钱兑换 II

求装满背包有几种方法，一般公式都是：dp[j] += dp[j - nums[i]]

只能先遍历硬币，再遍历容量，因为这样的结果得到的是组合数没有顺序，是组合数；

如果交换的话就会有顺序，是排列数

def change(self, amount: int, coins: List[int]) -> int:
dp=[0 for _ in range(amount+1)]
dp[0]=1
for c in coins:
for i in range(c,amount+1):
dp[i]+=dp[i-c]
return dp[-1]

True、False问题

公式：dp[i] = dp[i] or dp[i-num]

139. 单词拆分

有点像完全平方

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
n=len(s)
dp=[False]*(n+1)
dp[0]=True
for i in range(n):
for j in range(i+1,n+1):
if(dp[i] and (s[i:j] in wordDict)):
dp[j]=True
return dp[-1]

416. 分割等和子集

i是选择的数字个数，j是当前的值

我们需要的就是凑到j==target就好了

def canPartition(self, nums: List[int]) -> bool:
target=sum(nums)
if target%2!=0:
return False
target=target//2
dp=[False]*(target+1)
dp[0]=True
for i in range(len(nums)):
for j in range(target,-1,-1):
if j-nums[i]>=0:
dp[j]=dp[j-nums[i]] or dp[j]
return dp[-1]

最大最小问题

公式：dp[i] = min(dp[i], dp[i-num]+1)或者dp[i] = max(dp[i], dp[i-num]+1)

474. 一和零

01背包，但是容量变成用两个维度衡量

每次遍历物品前计算出物品两个维度上的容量

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 s in strs:
zero=s.count('0')
one=s.count('1')
for i in range(m,zero-1,-1):
for j in range(n,one-1,-1):
dp[i][j]=max(dp[i][j],dp[i-zero][j-one]+1)
return dp[-1][-1]

322. 零钱兑换

def coinChange(self, coins: List[int], amount: int) -> int:
dp=[0]+[float('inf')]*(amount)
for c in coins:
for i in range(c,amount+1):
dp[i]=min(dp[i-c]+1,dp[i])
return dp[-1] if dp[-1]!=float('inf') else -1

1049. 最后一块石头的重量 II

i是物品数，j是物品重量，题目可以转化为求重量为j的背包里装的最大重量。

一开始没想到如何转化成01背包问题

转化后和分割等和子集很像

def lastStoneWeightII(self, stones: List[int]) -> int:
if not stones:
return 0
target=sum(stones)//2+1
dp=[0]*(target+1)
for i in range(0,len(stones)):
for j in range(target,stones[i],-1):
dp[j]=max(dp[j],dp[j-stones[i]]+stones[i])
return sum(stones)-2*dp[-1]

279. 完全平方数

动态规划

可以看成找零钱问题

def numSquares(self, n: int) -> int:
can = [i*i for i in range(1,int(pow(n,0.5))+1) ]
dp = [0]+[float(inf)]*n
#最小值0的时候, 用了 0 枚硬币.
for c in can:
for i in range(1,n+1):
if i - c >=0:
dp[i] = min(dp[i], dp[i-c]+1)
return dp[-1]

BFS

层序遍历可以找到满足要求的最短路径

def numSquares(self, n: int) -> int:
from collections import deque
deq=deque()
visited=set()
deq.append((n,0))
while deq:
number,step=deq.popleft()
targets=[number-i*i for i in range(1,int(number**0.5)+1)]
for target in targets:
if target==0:return step+1
if target not in visited:
deq.append((target,step+1))
visited.add(target)
return 0

连续子序列问题

满足要求就是之前的状态+1

300. 最长递增子序列

动态规划

子问题：子序列的最长递增

base case:1

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

二分查找

def lengthOfLIS(self, nums: List[int]) -> int:
size = len(nums)
if size<2:
return size
cell = [nums[0]]
for num in nums[1:]:
if num>cell[-1]:
cell.append(num)
continue
l,r = 0,len(cell)-1
while l<r:
mid = l + (r - l) // 2
if cell[mid]<num:
l = mid + 1
else:
r = mid
cell[l] = num
return len(cell)

最长长不下降子序列

和上面问题的判断条件相反

n=int(input())
num=list(map(int,input().split()))
dp=[1]*n
for i in range(1,n):
for j in range(0,i):
if num[i]>=num[j]:
dp[i]=max(dp[j]+1,dp[i])
print(dp)

1143. 最长公共子序列

astr=input()
bstr=input()
an=len(astr)
bn=len(bstr)
dp=[[0 for _ in range(bn)] for _ in range(an)]
for i in range(an):
for j in range(bn):
if astr[i]==bstr[j]:
dp[i][j]=dp[i-1][j-1]+1
else:
dp[i][j]=max(dp[i][j-1],dp[i-1][j])
print(dp[-1][-1])

剑指 Offer 42. 连续子数组的最大和

最长连续子序列和

dp[i]是以nums[i]结尾的连续子数组的最大和

def maxSubArray(self, nums: List[int]) -> int:
dp=[float('-inf')]*len(nums)
for i in range(0,len(nums)):
dp[i]=max(nums[i],dp[i-1]+nums[i])
return max(dp)

152. 乘积最大子数组

由于两个负数相乘可以变成正数，所以要记录两个值，最大值和最小值，和当前值比较

def maxProduct(self, nums: List[int]) -> int:
res=nums[0]
premax=nums[0]
premin=nums[0]
for i in nums[1:]:
tmax=max(premax*i,premin*i,i)
tmin=min(premax*i,premin*i,i)
res=max(tmax,res)
premax=tmax
premin=tmin
return res

股票问题

• 明确股票有几种状态（卖出/买进，持有/不持有······）
• 第i天时股票各状态如何由前一天的状态转移过来
• dp初始化

121. 买卖股票的最佳时机

其实是贪心

取左边最小差值，区间最大利润

def maxProfit(self, prices: List[int]) -> int:
dp0 = 0
# 一直不买
dp1 = - prices[0]
# 只买了一次
dp2 = float('-inf') # 买了一次，卖了一次
for i in range(1, len(prices)):
dp1 = max(dp1, dp0 - prices[i])
dp2 = max(dp2, dp1 + prices[i])
return max(dp0, dp2)

122. 买卖股票的最佳时机 II

贪心

def maxProfit(self, prices: List[int]) -> int:
ans=0
for i in range(len(prices)-1):
if prices[i+1]-prices[i]>=0:
ans+=prices[i+1]-prices[i]
return ans

动态规划

两种状态：

• 当前持有股票
  • 之前就持有，现在保持
  • 之前没有，现在买的
• 当前没有股票
  • 之前就没有，现在保持
  • 之前有，现在卖掉了

def maxProfit(self, prices: List[int]) -> int:
dp=[[0,0]]*(len(prices)+1)
dp[0][0]-=prices[0]
for i in range(1,len(prices)):
dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i])
dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i])
return max(dp[-1][0],dp[-1][1])

123. 买卖股票的最佳时机 III

第二维是股票拥有的状态

def maxProfit(self, prices: List[int]) -> int:
dp=[[0]*5 for _ in range(len(prices))]
dp[0][1]-=prices[0]
dp[0][3]-=prices[0]
for i in range(1,len(prices)):
dp[i][0]=dp[i-1][0]
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])
dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i])
dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i])
dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i])
return dp[-1][-1]

188. 买卖股票的最佳时机 IV

允许成交k次，则状态有2k+1种

def maxProfit(self, k: int, prices: List[int]) -> int:
if not prices:
return 0
size=len(prices)
dp=[[0]*(2*k+1) for _ in range(size)]
for i in range(1,2*k+1):
if i%2!=0:
dp[0][i]-=prices[0]
for i in range(1,size):
for j in range(1,2*k+1):
if j%2==0:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i])
else:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i])
return dp[-1][-1]

309. 最佳买卖股票时机含冷冻期

3种状态要明确：

• 持有
• 不持有（可购买）
• 不持有（冷冻期）

def maxProfit(self, prices: List[int]) -> int:
dp=[[0]*3 for _ in range(len(prices))]
dp[0][1]-=prices[0]
for i in range(1,len(prices)):
dp[i][0]=max(dp[i-1][2],dp[i-1][0])#没有股票,能购买
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])#有股票
dp[i][2]=dp[i-1][1]+prices[i]#没有股票，冷冻期
return max(dp[-1])

714. 买卖股票的最佳时机含手续费

有两个状态，在卖出后再加收手续费

空间压缩后

def maxProfit(self, prices: List[int], fee: int) -> int:
dp=[0,-prices[0]]
for i in range(1,len(prices)):
dp[0]=max(dp[0],dp[1]+prices[i]-fee)
dp[1]=max(dp[1],dp[0]-prices[i])
return dp[0]

最后

以上就是健忘煎饼为你收集整理的小白的动态规划学习的全部内容，希望文章能够帮你解决小白的动态规划学习所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。