力扣刷题笔记 #05-2 二维动态规划
本文最后更新于:2023年3月18日 晚上
本文包含「动态规划」类型题中的:二维线性 DP、字符串匹配 DP、背包 DP 等。持续更新中。
题目描述:
方法1:
方法2:
方法3:
坑点:
动态规划(DP)适用于满足重叠子问题 + 最优子结构的问题,常用的方法有「记忆化搜索」、「递推」等。DP 的时间复杂度通常是「状态总数 $\times$ 每个状态向其他状态转移的次数」。
动态规划(DP)的一般步骤:
- 列出题目给的整体规模变量,例如 $n,m$
- 用局部变量 $i,j,k$ 描述一般状态,例如 $dp[i][j]$
- 观察上述一般状态的最后一步,例如判断 $s[i]==s[j]$
- 去掉最后一步,问题规模缩小,变成子问题,例如 $dp[i-1][j-1]$
- 得到状态转移方程,例如 $dp[i][j]=dp[i-1][j-1]+1$
- 初始边界值和最终状态,例如 $dp[i][0]$、$dp[0][j]$ 和 $dp[n][m]$
- 可选的转移优化,例如记忆化、前缀和等
二维线性 DP
需要用到一个二维数组进行转移,而转移的方向通常是相邻的左方、左上方、上方状态,因此可以采用滚动数组优化空间复杂度。
62. 不同路径 (M)
题目描述:一个机器人位于一个 m x n
网格的左上角,试图达到网格的右下角,求路径数目。
方法1:DP,用 $dp[i][j]$ 表示从左上角走到 $(i,j)$ 的路径数,首行和首列初始化为 1,时空复杂度均为 $O(n^2)$。
方法2:DP + 滚动数组,下一个状态只由最近两行的状态转移,因此可以用两行数组,空间复杂度为 $O(n)$。
方法3:组合数公式,从左上角到右下角的过程中,总共需要走 $m+n-2$ 步,其中必有 $m-1$ 步向下,其余向右。因此答案就是 $C^{m-1}_{m+n-2}$。数字较小可以直接用定义计算,时间复杂度 $O(\min(m,n))$,空间复杂度 $O(1)$。
拓展:63. 不同路径 II,路径中加入了障碍物,此时在递推时如果遇到障碍物,则直接将该点的状态置为零。需要注意的是,在初始化首行和首列时,如果遇到障碍物,则后续的位置都不可访问!
221. 最大正方形 (M)
题目描述:在一个由 '0'
和 '1'
组成的二维矩阵内,找到只包含 '1'
的最大正方形,并返回其面积。
方法1:暴力,对于每个元素 $1$,将其作为右下角,扫描确定其能构成的最大正方形,时间复杂度 $O(n^4)$。
方法2:二维线性 DP,$dp[i][j]$ 表示 $(i,j)$ 作为右下角能构成的最大正方形,状态转移时应从周边三个中取最小值,确保剩下三个角都能取到,时空复杂度均为 $O(n^2)$。
方法3:滚动数组,前三个状态都可以计算好,左上角的状态用临时变量存储,空间复杂度降到 $O(n)$。
799. 香槟塔 (M)
题目描述:把玻璃杯摆成金字塔的形状,其中第 $i$ 层有 $i$ 个玻璃杯,从最上方倒入 $k$ 杯香槟,求第 $n$ 层第 $m$ 杯的量。
方法1:二维 DP 递推,记 $dp[i][j]$ 为第 $i$ 行第 $j$ 杯所经过的水的流量(而不是最终剩余的水量),则 $dp[0][0]=k$,答案为 $\min(dp[n][m], 1)$。当 $dp[i][j]\leqslant 1$ 时,不会有水从杯子里溢出,则该状态不能转移到其他状态,否则会有 $dp[i][j]-1$ 的水等量地转移到下方两个杯子。时间复杂度 $O(nm)$,空间复杂度为 $O(n^2)$。
方法2:二维 DP + 滚动数组,空间优化到 $O(n)$。
OJ 数组弹出乘积的最大和 (M)
题目描述:给定两个等长的数组,其中一个支持 pop_front
,另一个支持 pop_front
和 pop_back
。每次各弹出一个元素,并将两个元素相乘后累加,求数组全部弹出后累加的最大值。
方法1:二维 DP,第一个数组弹出的顺序是固定的,用 $now$ 表示。$dp[i][j]$ 表示第二个数组剩下 $[i,j)$ 时的最大和,则初始 $dp[0][n]=0$,最终返回 $dp[i][i]$ 中的最大值(对角线)。每个状态有两种转移可能,时间复杂度 $O(n^2)$。
方法2:反向二维 DP,由于第一个数组弹出顺序固定,可以将题意逆向为 push
,则 $dp[i][j]$ 表示压入 $[i,j)$ 时的最大值,则初始 $dp[i][i]=0$,最终返回 $dp[0][n]$。沿着对角线遍历,时间复杂度 $O(n^2)$。
808. 分汤 (H)
题目描述:有 A 和 B 两种汤各 $n$ 毫升,现以等概率进行四种操作:$(4,0),(3,1),(2,2),(1,3)$,其中 $(a,b)$ 表示分走 $a$ 毫升的 A 汤和 $b$ 毫升的 B 汤。求 A 先分配完的概率 + AB 同时分配完的概率 / 2。
方法1:二维 DP + 浮点近似,用 $dp[i][j]$ 表示汤剩下 $(i,j)$ 时的答案,时间复杂度 $O(n^2)$,但是可以提前特判。
边界值 $dp[i][0]$ 表示 B 汤先分配完,此时答案为 $0$;$dp[0][0]$ 表示同时分配完,此时答案为 $1/2=0.5$;$dp[0][j]$ 表示 A 汤先分配完,答案为 $1$。最终结果时 $dp[n][n]$。
本题 $n<10^9$,按照 $O(n^2)$ 的复杂度不可能完成,但是由于返回值在正确答案 $10^{-5}$ 的范围内将被认为是正确的,而本题的结果显然随着 $n$ 递增而递增,测算发现在 $n\geqslant 179$ 时只需输出 $1.0$ 作为答案即可,可以特判。
方法2:记忆化搜索,依然需要先进行特判,再用 $vis$ 数组记录访问过的结果,时间复杂度 $O(n^2)$。
2435. 矩阵中和能被 K 整除的路径 (H)
题目描述:给定 m x n
的整数矩阵 grid
和一个整数 k
。从左上角出发,每一步只能往下或者往右,到达右下角。返回路径和能被 k
整除的路径数目。
方法1:记忆化搜索,显然要将路径和作为一个维度,用一个 vis[i][j][num]
表示从 $(i,j)$ 走到右下角且路径和模 $k$ 为 $num$ 的路径数,从左上角开始 DFS,右下角结束。最后返回 vis[0][0][0]
,时空复杂度均为 $O(mnk)$。
方法2:DP,发现搜索的方向具有无后效性,因此改用常数更小的 DP,$dp[i][j][num]$ 表示从左上角走到 $(i,j)$ 且路径和模 $k$ 为 $num$ 的路径数,初始值 $dp[0][0][grid[0][0]\;\%\;k]=1$,时空复杂度均为 $O(mnk)$。
或者:
方法3:DP + 滚动数组,前两个维度中,每组状态只由左边、上面两组状态转移过来,因此可以用两个 $n\times k$ 的数组交替存储。空间复杂度优化到 $O(nk)$。
坑点:采用第二个状态转移方程,更符合直觉,但是要注意负数取模防止越界!
字符串匹配 DP
字符串匹配是常见的 DP 问题背景,具体可分为下面两类:
给定两个字符串进行某种规则匹配,通常是二维线性 DP 表示两个子串。
给定一个字符串,从短序列到长序列扩展(如回文串),通常用一个二维数组表示区间的状态,但只会用到上三角。
5. 最长回文子串 (M)
题目描述:给一个字符串 s
,找到 s
中最长的回文子串。
方法1:暴力,两层循环,遍历区间起始位置和终止位置,然后判断这个区间是不是回文,复杂度 $O(n^3)$。
方法2:二维 DP,$P(i,j)$ 表示 $s[i\cdots j]$ 是否为回文串(布尔值),复杂度 $O(n^2)$。
在转移过程中,$dp[i][j]$ 仅为二维数组的上三角矩阵,且要注意扫描的顺序,从长度较短的字符串向长度较长的字符串进行转移。因此外层循环是
j++
,内层循环是i--
,才能确保无后效性。
方法3:中心扩散算法(回文串算法),如果画出方法 2 的 DP 矩阵,则会发现状态转移的路径都是沿着反对角线的直线,即所有状态在转移时的可能性都是唯一的,因此可以从每一种边界情况 $P(i, i)$ 开始扩散,尝试每种边界情况的状态转移最大步数。复杂度 $O(n^2)$。
方法4:Manacher 算法,利用回文串的对称性,将复杂度降低到 $O(n)$。
647. 回文子串 (M)
题目描述:给一个字符串 s
,统计并返回这个字符串中回文子串的数目。
方法1:二维 DP,同上题,先判断再累计求和,时间复杂度 $O(n^2)$。
方法2:中心扩散算法,两层循环,外层遍历回文中心点,内层向两边扩散,需要注意中心可能是 1 个字符或 2 个字符,因此内层循环有两次。时间复杂度 $O(n^2)$。
方法3:Manacher 算法,利用回文串的对称性,将复杂度降低到 $O(n)$。
Todo 516. 最长回文子序列 (M)
题目描述:给一个字符串 s
,找到 s
中最长的回文子序列,返回长度,子序列不要求连续。
方法1:二维 DP,$dp[i][j]$ 表示下标范围 $[i,j]$ 内的最长回文子序列的长度,
方法2:注意到,s
和 s.reverse()
的最长公共子序列(LCS)就是最长回文子序列,最快 $O(n\log n)$。
方法3:
1143. 最长公共子序列 (LCS) (M)
题目描述:给定两个字符串,返回两个字符串的最长公共子序列长度,子序列不需要连续。
方法1:DP,用 $dp[i][j]$ 存储 $s1$ 的前 $i$ 个字符与 $s2$ 中的前 $j$ 个字符,返回 $dp[n][m]$,时空复杂度均为 $O(nm)$。
方法2:DP + 滚动数组,用单行数组记录,再用一个额外变量存储 $dp[i-1][j-1]$ 即可,空间复杂度 $O(n)$。
方法3:下标化,用哈希表 + 向量记录 s2
中每个字符出现的下标,并用这些下标的倒序替换 s1
中对应字符,得到一个下标序列,求其最长上升子序列(LIS)即可得到答案。平均复杂度 $O(n \log n)$,当字符串稠密重复时退化到 $O(n^2 \log n)$。
举例:$s1 = \{a,b,c,d,b\}$,$s2 =\{b,c,a,b\}$,则 $a$ 对应在 $s2$ 的下标为 $2$,$b$ 对应下标为 $\{0,3\}$,$c$ 对应序号为 $1$,$d$ 对应为空,逆序后生成的新序列为 $\{2, 3, 0, 1, 3, 0\}$,其最长上升子序列为 $\{0,1,3\}$,对应的公共子序列为 $\{b, c, b\}$。
此处可以证明:s1、s2 的一个公共子序列和新序列的一个严格递增子序列一一对应。任意两个不同字符,如果能被选中作为公共子序列的一部分,其下标必严格递增。而之所以要逆序就是防止同一个位置的字符被多次选中。
退化:$s1 = \{a,a,a,a,a\}$,$s2 =\{a,a,a,a\}$,则生成的新序列长度为 $n\times m$,还要再乘上 $\log(n\times m)$。当然如果确保无重复,则可以保证复杂度不退化。
72. 编辑距离 (H)
题目描述:给定两个字符串,返回将 s1
修改成 s2
需要的最少操作数,一次操作可以是插入、删除、替换一个字符。
方法1:DP,用 $dp[i][j]$ 存储 $s1$ 的前 $i$ 个字符与 $s2$ 中的前 $j$ 个字符,返回 $dp[n][m]$,时空复杂度均为 $O(nm)$。
当新来的两个字符相等时,不会增加编辑距离,因此由左上角转移。当两个字符不相等时,有三种转移可能:
- 通过替换一个 $s1$ 字符到 $s2$ 字符(或反之),代价为 $dp[i-1][j-1] + 1$
- 通过删除一个 $s1$ 字符,代价为 $dp[i-1][j]+1$
- 通过删除一个 $s2$ 字符,代价为 $dp[i][j-1]+1$
方法2:DP + 滚动数组,用单行数组记录,再用一个额外变量存储 $dp[i-1][j-1]$ 即可,空间复杂度 $O(n)$。
10. 正则表达式匹配 (H)
题目描述:给定字符串 s
和模式 p
,实现一个支持 .
和 *
的正则表达式匹配,其中 .
匹配任意单个字符,*
匹配零或多个前一个字符。
方法1:正向扫描,但是不知道 *
该替换成多少个字符,例如:aaaa
和 a*
、a*a
、a*aa
,要考虑后面跟着的字符。同理反向扫描也得考虑 a*
、aa*
、aaa*
。实际操作中可以用 DFS + 记忆化处理,复杂度为 $O(mn)$。
方法2:DP,用 $f[i][j]$ 表示 $s$ 的前 $i$ 个字符与 $p$ 中的前 $j$ 个字符是否能够匹配。复杂度为 $O(mn)$。
字母 + 星号的组合在匹配时,要么匹配掉
s
的一个字符,转移到 $f[i-1][j]$ 或 $f[i][j-2]$;要么不匹配直接消去,转移到 $f[i][j-2]$。此外,匹配成功仅当两方相同或者一方是.
,写成函数 $\mathrm{matches}$,状态转移方程如下:
坑点:
- $f[0][0]$ 不是表示首个字符,而是两个空字符串,因此初始化为 1;DP 数组初始化的时候也要注意维数 +1。
- 字母 + 星号匹配时,依然有可能转移到 $f[i][j-2]$,这是因为存在「字母 + 星号的组合假匹配,直接消失才能成功」的情况,例如
a
和aa*
。
背包 DP
背包问题是二维线性 DP 的分支,其常见类型有:01 背包、完全背包、多重背包等问题。注意部分背包问题本质是贪心算法,此处不展开讨论。
首先介绍是 01 背包问题,这类问题中「每个物品最多只能放一次」。这类问题中题目包含:
背景:共有 $n$ 件物品,最大容量为 $m$ 的背包。第 $i$ 件物品的价值是 $v[i]$,重量为 $w[i]$。
状态:$dp[i][j]$ 表示前 $i$ 件物品以某种组合能够放进容量为 $j$ 的背包的最大价值,考虑第 $i$ 件物品放或不放。
初始化:数组大小至少为 $n \times (m+1)$,初始所有元素都为零,首行 $dp[0][w[0]\cdots m]=v[0]$。
优化思路:可以用滚动数组优化空间复杂度,注意此时需要倒推防止覆盖,倒推的下限也可以优化。
1 |
|
416. 分割等和子集 (M)
题目描述:给定一个只包含正整数的数组。判断是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
方法1:排序 + 贪心?先划分大数再划分小数,但无法得到最优解,因为此题不满足贪心选择性,先划分的数不一定属于该子集,会被后面的数影响。
方法2:记忆化搜索,目标是找到 $sum/2$ 的元素,对每个数有两种分支。用 $vis$ 数组记忆,时间复杂度 $(n\cdot sum)$。
方法3:01 背包,$dp[i][j]$ 表示前 $i$ 个元素能否组成 $j$ 的和,目标是 $dp[n][sum/2]$。也可以更直接点,用 $dp[i][j]$ 表示前 $i$ 个元素放进容量 $j$ 的背包的最大值,目标是 $dp[n][sum/2]==sum/2$。时间复杂度 $(n\cdot sum)$。
1049. 最后一块石头的重量 II (H)
题目描述:给定整数数组表示一堆石头的重量,每次可从中选取两块石头进行粉碎,如果石头重量相等,则两块石头都被完全粉碎;否则较小者将完全粉碎,较大者重量变为二者之差,最后至多剩下一块石头,返回其最小的可能重量。
贪心分析:如果将石头分为两堆,每次各取出一个石头进行粉碎,则两边会减少相同重量。为此,我们尽量将石头平均分到两边, 使得两边重量之差的绝对值最小化。最后剩余的一堆中的那块石头,就是最小的可能重量。
贪心选择性证明:会不会出现一堆没有石头,而另一堆不止一块石头的情况呢?如果会这样,则要继续粉碎,从多余的那堆中取出较小的一块石头移入另一堆,继续粉碎。但移入操作让重量之差的绝对值变得更小,则与一开始的划分矛盾,不可能出现。
方法:01 背包,本题可转化为在容量为 $sum/2$ 的背包中,放入物品重量和价值均为 $stones_i$ 的问题,时间复杂度 $O(n\cdot sum)$,空间复杂度最低为 $O(sum)$。
494. 目标和 (M)
题目描述:给定一个正整数数组与目标,在每个整数前面添加正负号,求运算结果等于目标的不同表达式数目。
方法1:记忆化搜索,用 $vis[i][j]$ 表示考虑前 $i$ 个数结果为 $j$ 的数目,从 $vis[n-1][target]$ 开始搜索,注意数组的第二维可能是负数,可以采用哈希表实现。复杂度 $O(n\cdot sum)$。
方法2:二维 DP,$dp[i][j]$ 同上,直接递推,时空复杂度均为 $O(n\cdot sum)$。
方法3:01 背包,记所有正数的和为 $x$,负数为 $sum-x$,要求 $x-(sum-x)=target$,则 $x=(target+sum)/2$。该值必定非负。提前特判奇数情况、$target>sum$ 情况,剩下的就是求装满容量为 $x$ 的背包,有几种方法。
474. 一和零 (M)
题目描述:给定一组二进制字符串,从中选取一个子集,子集中最多有 m
个 0
和 n
个 1
。求最大子集长度。
本题易混淆为多重背包问题,实际上每个物品还是只能选一次,还是 01 背包,只是背包的容量有两个维度。
方法:多维 01 背包,$dp[i][j]$ 表示两种物品的容量分别为 $i$ 和 $j$ 时的最大子集,由于涉及高维,这里直接采用滚动数组节约空间,倒着递推。每个串的价值都是 $1$,转移方程如下。复杂度 $O(mn)$。
Todo 2518. 好分区的数目 (H)
题目描述:
方法1:
方法2:
方法3:
以下是完全背包问题,这类问题中「每种物品可以放无限多次」。这类问题中题目包含:
背景:共有 $n$ 件物品,最大容量为 $m$ 的背包。第 $i$ 件物品的价值是 $v[i]$,重量为 $w[i]$。
状态:$dp[i][j]$ 表示前 $i$ 件物品以某种组合能够放进容量为 $j$ 的背包的最大价值,考虑第 $i$ 件物品放多少个。
初始化:数组大小至少为 $n \times (m+1)$,初始所有元素都为零,首行要分段处理。
复杂度分析:每个状态可以由若干个状态转移,时间复杂度 $O(n\cdot \sum(m/w[i]))$。
优化思路:用滚动数组优化空间复杂度,但此时正推,这样就保证当访问 $dp[j-w[i]]$ 时,该值已经考虑过加入物品 $i$,反映了完全背包可以重复选择的特点!时间复杂度 $O(nm)$。
1 |
|
一种常见的变体是要求背包恰好凑满,求物品组合数或最少物品个数,这里也给出模板:
1 |
|
518. 零钱兑换 II (M)
题目描述:给一个整数数组 coins
表示不同硬币面额,一个整数表示总金额。计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个,硬币面额不重复。
方法1:完全背包,$dp[i][j]$ 表示用前 $i$ 种硬币凑成 $j$ 的组合数,本题的特点在于不凑满的背包是不合法的,因此初始化首行时要间隔,状态转移方程也要修改。
方法2:完全背包 + 滚动数组,注意要初始化 $dp[0]=1$,理解为没有硬币时也有一种组合,再开始考虑第一种。
由于外层循环先遍历 $coins$ 数组,在内层循环中,可以确保硬币面额在排列中的顺序,不会重复考虑一个组合。
322. 零钱兑换 (M)
题目描述:同上,但返回的是可以凑成总金额所需的最少的硬币个数,如果不存在则返回 $-1$。
方法1:完全背包。$dp[i][j]$ 表示用前 $i$ 种硬币凑成 $j$ 的最少个数,本题由于转移方程用到了 $\min$,所以初始值应该设为 0x3f
,只有间隔位置的元素可以凑成,且 $dp[0][0]=0$。但是由于总金额过大,该方法会超时。
方法2:完全背包 + 滚动数组,注意要初始化 $dp[0]=0$,理解为没有硬币时也可以凑齐零元。
TODO 377. 组合总和 IV (M)
题目描述:给定由不同整数组成的数组 nums
和一个目标数。从 nums
中找出总和为目标数的元素组合的个数。顺序不同序列被视为不同的组合。
方法1:完全背包。
方法2:
以下是多重背包问题,这类问题中「每种物品各有一个指定的次数上限」。这类问题中题目包含:
背景:共有 $n$ 件物品,最大容量为 $m$ 的背包。第 $i$ 件物品的价值是 $v[i]$,重量为 $w[i]$,其最多可装 $s[i]$ 件。
状态:$dp[i][j]$ 表示前 $i$ 件物品以某种组合能够放进容量为 $j$ 的背包的最大价值,考虑第 $i$ 件物品放多少个。
初始化:数组大小至少为 $n \times (m+1)$,初始所有元素都为零,首行要分段处理。
复杂度分析:每个状态可以由若干个状态转移,时间复杂度 $O(n\cdot \sum s[i])$。注意此时即使用了滚动数组正推,也不能省略内层循环 $0\leqslant k\leqslant s\left[ i \right]$,因为在 $dp[j]$ 的时候不知道是否达到上限。
优化思路:换个思路,我们可以将多重背包转化为 01 背包问题,只需要将每个物品扁平化为 $s[i]$ 件相同物品。但这样复杂度还是 $O(n\cdot\sum s[i])$。一个巧妙的办法是采用二进制压缩,将物品拆分为 $1,2,4\cdots$ 个,使其能够表达完整物品又压缩了空间,复杂度 $O(n\cdot \sum\log s[i])$。
1 |
|