力扣刷题笔记 #05-2 二维动态规划

本文最后更新于:2023年3月18日 晚上

本文包含「动态规划」类型题中的:二维线性 DP、字符串匹配 DP、背包 DP 等。持续更新中。

题目描述

方法1

方法2

方法3

坑点

动态规划(DP)适用于满足重叠子问题 + 最优子结构的问题,常用的方法有「记忆化搜索」、「递推」等。DP 的时间复杂度通常是「状态总数 $\times$ 每个状态向其他状态转移的次数」。

动态规划(DP)的一般步骤:

  1. 列出题目给的整体规模变量,例如 $n,m$
  2. 用局部变量 $i,j,k$ 描述一般状态,例如 $dp[i][j]$
  3. 观察上述一般状态的最后一步,例如判断 $s[i]==s[j]$
  4. 去掉最后一步,问题规模缩小,变成子问题,例如 $dp[i-1][j-1]$
  5. 得到状态转移方程,例如 $dp[i][j]=dp[i-1][j-1]+1$
  6. 初始边界值最终状态,例如 $dp[i][0]$、$dp[0][j]$ 和 $dp[n][m]$
  7. 可选的转移优化,例如记忆化、前缀和等

二维线性 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_frontpop_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:注意到,ss.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:正向扫描,但是不知道 * 该替换成多少个字符,例如:aaaaa*a*aa*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}$,状态转移方程如下:

坑点

  1. $f[0][0]$ 不是表示首个字符,而是两个空字符串,因此初始化为 1;DP 数组初始化的时候也要注意维数 +1。
  2. 字母 + 星号匹配时,依然有可能转移到 $f[i][j-2]$,这是因为存在「字母 + 星号的组合假匹配,直接消失才能成功」的情况,例如 aaa*

背包 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 原始数组,无优化
vector<vector<int>> dp(n, vector<int>(m + 1, 0));
for(int i = w[0]; i <= m; i++) dp[0][i] = v[0];
for(int i = 1; i < n; i++){
for(int j = 0; j <= m; j++){
dp[i][j] = dp[i - 1][j];
if(j >= w[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
}
}
return dp[n - 1][m];

// 滚动数组,倒推防止覆盖
vector<int> dp(m + 1, 0);
for(int i = 0; i < n; i++)
for(int j = m; j >= w[i]; j--)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
return dp[m];

// 多维 01 背包,还是采用滚动数组 + 倒推,w1 上限为 m,w2上限为 t
vector<vector<int>> dp(m + 1, vector<int>(t + 1, 0));
for(int i = 0; i < n; i++)
for(int j = m; j >= w1[i]; j--)
for(int k = t; k >= w2[i]; k--)
dp[j][k] = max(dp[j][k], dp[j - w1[i]][k - w2[i]] + v[i]);
return dp[m][t];

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)

题目描述:给定一组二进制字符串,从中选取一个子集,子集中最多m0n1。求最大子集长度。

本题易混淆为多重背包问题,实际上每个物品还是只能选一次,还是 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 原始数组,无优化,多了一层循环遍历个数
vector<vector<int>> dp(n, vector<int>(m + 1, 0));
for(int i = w[0]; i <= m; i++) dp[0][i] = i / w[0] * v[0];
for(int i = 1; i < n; i++)
for(int j = 0; j <= m; j++)
for(int k = 0; k * w[i] <= j; k++)
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
return dp[n - 1][m];

// 滚动数组最终版,正推,考虑重复选择
vector<int> dp(m + 1, 0);
for(int i = 0; i < n; i++)
for(int j = w[i]; j <= m; j++)
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
return dp[m];

一种常见的变体是要求背包恰好凑满,求物品组合数最少物品个数,这里也给出模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 最少物品个数,原始数组
vector<vector<int>> dp(n, vector<int>(m + 1, 0x3f3f3f3f));
for(int i = 0; i * w[0] <= m; i++) dp[0][i * w[0]] = i; // 间隔赋值
for(int i = 1; i < n; i++)
for(int j = 0; j <= m; j++)
for(int k = 0; k * w[i] <= j; k++)
dp[i][j] = min(dp[i][j], dp[i - 1][j - k * w[i]] + k);
return dp[n - 1][m] == 0x3f3f3f3f ? -1 : dp[n - 1][m];

// 最少物品个数,滚动数组
vector<int> dp(m + 1, 0x3f3f3f3f);
dp[0] = 0;
for(int i = 0; i < n; i++)
for (int j = w[i]; j <= m; j++)
dp[j] = min(dp[j], dp[j - w[i]] + 1);
return dp[m] == 0x3f3f3f3f ? -1 : dp[m];

// 物品组合数,原始数组
vector<vector<int>> dp(n, vector<int>(m + 1, 0));
for(int i = 0; i * w[0] <= m; i++) dp[0][i * w[0]] = 1;
for(int i = 1; i < n; i++)
for(int j = 0; j <= m; j++)
for(int k = 0; k * w[i] <= j; k++)
dp[i][j] += dp[i - 1][j - k * w[i]];
return dp[n - 1][m];

// 物品组合数,滚动数组
vector<int> dp(m + 1, 0);
dp[0] = 1;
for(int i = 0; i < n; i++)
for (int j = w[i]; j <= m; j++)
dp[j] += dp[j - w[i]];
return dp[m];

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 原始数组,无优化,多了一层循环遍历个数
vector<vector<int>> dp(n, vector<int>(m + 1, 0));
for(int i = w[0]; i <= m; i++)
dp[0][i] = (i / w[0] < s[0] ? i / w[0] : s[0]) * v[0];
for(int i = 1; i < n; i++)
for(int j = 0; j <= m; j++)
for(int k = 0; k * w[i] <= j && k <= s[i]; k++)
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * w[i]] + k * v[i]);
return dp[n - 1][m];

// 扁平化,用 W 和 V 存储扁平化数组,再接 01 背包
vector<int> W, V;
for(int i = 0; i < n; i++){
for(int t = 1; t <= s[i]; t <<= 1){
s[i] -= t;
W.push_back(w[i] * t);
V.push_back(v[i] * t);
}
if(s[i] > 0){
W.push_back(w[i] * s[i]);
V.push_back(v[i] * s[i]);
}
}
vector<int> dp(m + 1, 0);
for(int i = 0; i < W.size(); i++)
for(int j = m; j >= W[i]; j--)
dp[j] = max(dp[j], dp[j - W[i]] + V[i]);
return dp[m];

力扣刷题笔记 #05-2 二维动态规划
https://hwcoder.top/LeetCode-DP-2
作者
Wei He
发布于
2022年10月2日
许可协议