← 博客

动态规划

灵神题单

线性dp

Alt text

排列型

外层遍历target，内层遍历可用的数字

70. 爬楼梯

这里的1和2也可以无数次被用，并且不同顺序算为不同的答案

lc 377:

排列型：外层target，内层nums

与完全背包的不同点在于：[1,3],[3,1]被算作两个不同的答案。 如果用cache修饰 dfs, 则不能使用全局变量res来计算个数，必须把res作为 dfs的返回值。

139: 单词拆分

leetcode可以通过leet和code组成。如果code在 wordSet中，那么dp[9]=dp[4]

入门DP

House Robber

LC 198

空间优化。

213 打家劫舍 II

所有房子围成一圈。考虑只能偷**前(n-1)个房子的情况，和只能偷后(n-1)**个房子的情况，因为第一个房子和最后一个房子肯定不能同时偷！

740. 删除并获得点数

如果选了x，删除并且获得点数，则所有x+1和x-1都一起都被删掉，所以把所有其它的x都删掉并获得点数

则，选择x,可以获得x*cnt[x],且不能获得x+1/x-1的点数

最大子数组和

kadane 算法

1
2
3
4
5
6
7

def kadane(arr):
    res=arr[0]
    cur=arr[0]
    for i in range(1,len(arr)):
        cur=max(cur+arr[i], arr[i])
        res=max(res, cur)
    return res

LC 53

dp[i]存放以当前元素结尾的最大和

dp[i]=max(dp[i-1]+nums[i], nums[i])

空间优化：

1
2

f=max(x, f+x)
res=max(f, res)

LC 1749 任意子数组和的绝对值的最大值

遍历过程中，保持一个以当前元素结尾的最大和与最小和。绝对值最大->子数组和最大或最小

2321. 拼接数组的最大分数

怎么换，能让 nums1 的数组和最大化？其实就是找一个子数组，答案为 s1+diff(nums2子数组-nums1 子数组)，也就是最大化 diff 数组的子数组和

网格图 DP

基础题只需要做：63. 不同路径 II

dp[i+1][j+1]表示遍历到grid[i][j]时的方案数。初始化时，dp[0][1]=1

329. 矩阵中的最长递增路径

记忆化搜索，dfs(i,j)表示从这个格子开始往四周搜索，找到最长的长度之后，填入dp[i][j]

最大子数组和

定义状态 f[i] 表示以 a[i] 结尾的最大子数组和，不和 i 左边拼起来就是 f[i]=a[i]，和 i 左边拼起来就是 f[i]=f[i−1]+a[i]，取最大值就得到了状态转移方程 f[i]=max(f[i−1],0)+a[i]

152. 乘积最大子数组

注意初始化数组大小为n. minF[0]=maxF[0]=nums[0]
用两个数组表示到某个数为止的最大/最小子数组乘积

minF[i]=min(minF[i]*x, x, maxF[i]*x)
maxF[i]=max(minF[i]*x, x, maxF[i]*x)

01背包

恰好型

恰好+求方案数（416. 分割等和子集）

记忆化搜索

dfs(start, target) 表示nums[start]到结尾，能否找到一个和为target的子集. target=s//2

时空复杂度O(n*sum)

一维dp

可以做到空间优化，O(sum)。
内部必须倒序遍历。
dp[i]表示数组中能否找到一个子集，子集的和为i.
外部枚举所有值，比如枚举到一个值c。内部枚举target, dp[i]=dp[i] or dp[i-c].
如果正序枚举，那么这个c可能会被用两次。比如c=1, 一开始设置dp[1]=dp[1-1]=True, 然后又会设置dp[2]=dp[2-1]=dp[1]=True. 则这个值会被用两次

恰好+验证合法性（1049. 最后一块石头的重量 II）

恰好+求最大价值（2915. 和为目标值的最长子序列的长度）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def knapsack_exact_max(items, C):
    NEG_INF = -10**18
    dp = [NEG_INF] * (C + 1)
    dp[0] = 0

    for w, v in items:
        for c in range(C, w - 1, -1):
            if dp[c - w] != NEG_INF:
                dp[c] = max(dp[c], dp[c - w] + v)

    return dp[C]  # 如果仍是 NEG_INF，说明恰好凑不出

≤ 约束下最值

这就是经典的01背包，如2291题。
dp[budget]表示最多花费budget时，能获得的最大收益

二维背包

474, 2431. 多一层循环即可！

遍历顺序

这两道题对于理解遍历的本质有帮助

3180. 执行操作可获得的最大总奖励 I

为什么一定要排序？尽可能获得最大的奖励，必须从小到大取物品！如果遍历的时候没有排序，那么可能会先取大物品，这样就没办法取到小物品了。

假设外部物体遍历到x, 此时尝试更新可能的奖励j. 那么必须有j-x < x，才能更细腻。因为j-x代表目前有的价值

3489. 零数组变换 IV

对每个位置的目标x，按顺序遍历所有query。
如果这个query包含了该位置，则尝试更新dp[j]，即应用这个query后，能否使和为j.
遍历到某个query时，看看该位置的目标是否已经达成,dp[x]是否为true.如果为true, 则不用继续遍历query。记录此位置需要的query前缀位置i。
对所有位置，取前缀位置i的最大值

完全背包

有 n个物品，第i个物品的体积为w[i], 价值为v[i]，每个物体能选无限次，容量为 capacity，求最大价值。

dfs(i, c)=dfs(i-1, c)+dfs(i, c-w[i])

LC 322 coin change

零钱价值视为体积，每个的价值为1. amount视为capacity，求体积恰好为capacity的时候，最小价值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def coinChange(self, coins: List[int], amount: int) -> int:
    #dfs(i, c)表示遍历到第 i个硬币的时候，当前总价值为 c，所需要的最少硬币数
    @cache
    def dfs(i, c):
        if i<0:
            return 0 if c==0 else inf #容量需恰好为 amount
        if coins[i]>c:
            return dfs(i-1, c)
        return min(dfs(i-1, c), dfs(i, c-coins[i])+1)
    res=dfs(len(coins)-1, amount)
    return res if res<inf else -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def coinChange(self, coins: List[int], amount: int) -> int:
    n=len(coins)
    dp=[[inf]*(amount+1) for _ in range(n+1)]
    dp[0][0]=0
    for i, x in enumerate(coins):
        for j in range(amount+1):
            if x<=j:
                dp[i+1][j]=min(dp[i+1][j-x]+1, dp[i][j])            
            else:
                dp[i+1][j]=dp[i][j]
    return dp[n][amount] if dp[n][amount]<inf else -1

518. 零钱兑换 II

可以与377对比。

此题的本质是：“求组合”，外层nums，内层target。

最长公共子序列

需要单独处理i==0或j==0的情况，即完全不用另一个字符串的情况

LC 1143

dfs(i, j)表示遍历到s[i]和t[j]时，从前往后最长公共子序列的长度。

  1. 如果s[i]==t[j]，必须选当前字符

dfs(i, j)=dfs(i-1, j-1)+1;

  1. 如果s[i]!=t[j]

dfs(i, j)=max(dfs(i, j-1), dfs(i-1, j))

LC 72 编辑距离

dfs(i, j)表示遍历到s[i]和t[j]时，为保持两个字符串相同，所需要的操作数

s: rorse, t: rose

此处遍历到这两个字符不同，如果对 S 执行删除操作，相当于

dfs(i, j)=dfs(i-1, j)+1

s: ct, t: cat

如果此时对S执行添加操作，相当于

dfs(0, 0)=0, dfs(0, 1)=dfs(0, 0)+1=1

dfs(i, j)=dfs(i, j-1)+1

类似地，对 S 执行替换操作，相当于

dfs(i, j)=dfs(i-1, j-1)+1

当遍历到s[i]和t[j]时, 如果他们不相同，则需要遍历三种情况，看看当前字母前面的字母是什么样子的。所以，

dfs(i, j)=min(dfs(i-1, j), dfs(i, j-1), dfs(i-1, j-1))+1

💡注意边界条件。dp[0][0]=0, dp[i][0]=i, dp[0][j]=j. 初始化为(m+1)*(n+1)的矩阵，dp[i][j]表示遍历到word1的第i个和word2的第j个，也就是word1[i+1], word2[j+1]

97. 交错字符串

注意这一题需要单独处理dp数组中i=0或j=0的情况！

44. 通配符匹配

p中字符可以为字母，*，？

*匹配零个或多个字母，？匹配任意一个字母

p[j]==*时，dp[i+1][j+1]= dp[i+1][j] or dp[i][j+1]
分别代表匹配0个字符串和匹配多个字符串

10. 正则表达式匹配

dp[i][j]表示s(0,i-1)与p(0,j-1)匹配. 每次比较s[i], p[j],来确定dp[i+1][j+1]的值

  • base case: s为空，p为空，True；s为空，p为xx类型，True。如何初始化？从j=1开始遍历，确定dp[0][j+1]的值。只有当p[j]==’*‘且 dp[0][j-1]为True时，dp[0][j+1]才为True

  • 如果匹配，dp[i+1][j+1]直接为True

  • 如果p[j]为*，且s[i]与p[j-1]匹配，则有三种可能，匹配一个字母，匹配零个字母，匹配多个字母

  • 如果p[j]为*，且s[i]与p[j-1]不匹配，则看看匹配零个字母这种方案是否可行

115. 不同的子序列

dp[i][j]表示s(0,i-1)与t(0,j-1)匹配的方案数量

如果s[i]==t[j]，则可以用s[i],也可以不用 如果不相等，不能用 s[i]

比如s=bbbb, t=bb。当i=2, j=1时就是考虑bb在bbb中可以出现几次

如果放，则考虑b可以在bb中能出现几次(i=1, j=0)

如果不放，代表bb在之前已经出现过了，考虑bb在bb中能出现几次(i=1, j=1)

LC 3290 最高乘法得分

a = [3,2,5,6], b = [2,-6,4,-5,-3,2,-7] 从 b的最后一个元素开始思考。

如果选它，那么考虑[3,2,5]和[2,-6,…,2]中间元素相乘的最大值。
如果不选它，那么考虑[3,2,5,6]和[2,-6,…,2]中间元素相乘的最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def maxScore(self, a: List[int], b: List[int]) -> int:
    #dp[i][j]=max(dp[i][j-1], dp[i-1][j-1]+a[i-1]*b[j-1])
    m=len(a)
    n=len(b)
    dp=[[-inf]*(n+1) for _ in range(m+1)]
    dp[0]=[0]*(n+1)
    for i in range(m):
        for j in range(n):
            dp[i+1][j+1]=max(dp[i+1][j], dp[i][j]+a[i]*b[j])
    return dp[m][n]
    #dp[1][2]=max(dp[1][1], dp[0][1]+a[0]*b[1])

初始化dp[0]=[0]*(n+1)，因为考虑到数组 a遍历到0（还没开始遍历的时候），不管b数组遍历到哪里，初始的乘积和为 0. 也可思考循环赋值过程，如最后一行的注释。

区间DP

状态转移方向：从中间到两边，i倒序遍历，j正序遍历

516. 最长回文子序列： 选/不选

1
2
3
4

if s[i]==s[j]:
    dfs(i, j)=dfs(i+1, j-1)+2
else:
    dfs(i, j)=max(dfs(i+1, j), dfs(i, j-1))

注意递推的遍历顺序。

1
2
3

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

5. 最长回文子串

dp[i][j]表示s[i:j+1]是否为回文。
dp[i][j]=dp[i-1][j+1] and s[i]==s[j]
所以i需要倒序遍历，j正序遍历

1039. 多边形三角剖分的最低得分

区间dp一定是从中间往两边蔓延。

1

dp[i][j]=values[i]*values[j]*values[k]+dp[i][k]+dp[k][j]

dp如何初始化？看递归的尽头是什么。
比如这题考虑i,k,j=0,1,2时，dp[i][k]必须为0. 所以所有dp[i][i+1]=0

1130. 叶值的最小代价生成树

中序遍历的特点：数组中的任意连续子区间 [i, j] 都对应着二叉树中的一个完整子树

arr = [6,2,4]

可以知道，有两种组成树的方式，因为有两种方法去划分这个 array，一个是 6,(2,4),一个是(6,2),4

dfs(left, right)返回从 array[left, right]构成的树的（非叶子节点最小和，区间中的最大值）

96. 不同的二叉搜索树

G[n]表示由n个节点组成的二叉搜索树的个数

f[i]表示其中以i为root的二叉搜索树的个数

想象i为root，那么它的左边节点一共有i-1个，右边节点一共有n-i个。而它的左子树和右子树都是二叉搜索树，所以对应的个数为G[i-1]和G[n-i]

最长递增子序列

回溯->记忆化搜索->动态规划
贪心+二分可实现最优

300. 最长递增子序列

定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度，注意 nums[i] 必须被选取。

673. 最长递增子序列的个数

cnt[i]为考虑以 nums[i] 结尾的最长上升子序列的个数

dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的最长上升子序列的长度

图 DP

787. K 站中转内最便宜的航班

dp[t][i]表示经过t-1次转机，到达i城市的最小费用。
模拟每次转机，即从0到k遍历转机次数，每一次遍历时，都遍历所有航班，用来更新：到达每个目的地，正好x次转机所需要的最小费用。

状态机 DP

一般定义 f[i][j] 表示前缀 a[:i] 在状态 j 下的最优值。
j一般很小。

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

#0:不操作，1:第一次持有，2:第一次不持有，3:第二次持有，4:第二次不持有

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

1:第一次持有，2:第一次不持有，3:第二次持有，4:第二次不持有，直到第K次

需要注意的是

  • 初始化：不管在哪一天，当没有任何操作的时候，值为-inf
  • 返回答案：返回最后一天的所有状态中的最大值。

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

冷冻期：如果当天卖出了，则第二天不可以买入
0: 当天卖出，不持有
1: 持有状态
2: 不持有，且非当天卖出

划分型DP

139. 单词拆分

dp[i+1]表示字符串s(0,j)可以被字典组成。
对于每个结尾i,枚举起点j，看s[j:i+1]是否在字典中并且dp[j]==True

91. 解码方法

dp[i+1]表示可以解码s(0,i)这一段的方法数

if s[i]可以作为两位数的第二位，dp[i+1]+=dp[i-1]

if s[i]>0, dp[i+1]+=dp[i]

子矩形 DP

221. 最大正方形

状态压缩

  • 定义 f[S] 表示已经排列好的元素（下标）集合为 S 时，和题目有关的最优值。通过枚举当前位置要填的元素（下标）来转移。
  • 定义 f[S] 表示可以选的元素（下标）集合为 S 时，和题目有关的最优值。通过枚举当前位置要填的元素（下标）来转移。

枚举真子集, mask代表集合（当前的状态）

1
2
3
4
5

sub = (mask - 1) & mask  # 枚举真子集
while sub > 0:
    # 分成两组: sub 和 mask^sub
    f[mask] = min(f[mask], f[sub] + f[mask ^ sub])
    sub = (sub - 1) & mask
  • 数这个集合中的人数：bin(mask).count(‘1’)

526. 优美的排列

dp[i][state] 表示：已经填了前 i 个位置，使用的数字状态为 state 的方案数

465. 最优账单平衡

transactions = [[0,1,10],[2,0,5]]对于这个交易序列，可以得到最后每个人的经济情况： -5 10 -5

f[mask] = 让mask表示的这些人结清债务,需要的最少转账次数

  • 这些人的总和不为0，则f[mask]=inf
  • 总和为0，则最坏结果为f[mask]=[S]-1 (集合中元素个数-1)
  • 优化方案：f[mask] = min(f[子集1] + f[子集2])

数位 DP

视频讲解

1
2
3
4

def dfs(i:int, upper_limit:bool, lower_limit:bool):
    #i<diff_lh and lower_limit<=>我们正在填前导0
    #diff_lh=len(upper)-len(lower)
    #lo=lower[i] if lower_limit else 0

一般用upper和lower这两个字符串来表示可选数字的上界和下界

比如上界是654，如果第一位数取了6，那么第二位数的上界必须是5

2999. 统计强大整数的数目

这里又有限制：每个数位至多是limit
limit=5, upper=74386
如果把hi变成了5，k取5，就是5xxxx
但这个没有触及到上界～这样传到i=1的时候，会让limit_high=True, 那么第二位只能取到4，无法取到5
这样的话比如55555这个答案就被遗漏了～

树形 DP

968. 监控二叉树

对于一个节点，有三个方法可以被监控

  • 自己装摄像头 （蓝）
  • 自己没装，parent 装摄像头 （黄）
  • 自己没装，child 装摄像头 （红）

考虑节点为蓝/黄/红

  • 当节点为蓝时：子节点可以为蓝/黄/红，则答案为：min(左蓝，左黄，左红)+min(右蓝，右黄，右红)+1
  • 黄：子节点不可能是黄色，可以是蓝红。则答案为：min(左蓝，左红)+min(右蓝，右红)
  • 红：子节点不可能是黄色，并且至少有一个儿子是蓝色。则答案为：min(左蓝+右红，右蓝+左红，左蓝+右蓝)

题目中的祖先（根节点）应当为蓝/红，dfs 函数返回三种情况所需的最少摄像头数量

其它线性DP

一维DP

2944. 购买水果需要的最少金币数

dfs(i) 表示在购买第 i 个水果的前提下，获得第 i 个及其后面的水果所需要的最少金币数