力扣刷题笔记 #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_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}$，状态转移方程如下：

坑点：

  1. $f[0][0]$ 不是表示首个字符，而是两个空字符串，因此初始化为 1；DP 数组初始化的时候也要注意维数 +1。
  2. 字母 + 星号匹配时，依然有可能转移到 $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
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)

题目描述：给定一组二进制字符串，从中选取一个子集，子集中最多有 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
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];
算法笔记 > 力扣刷题
#Algorithm
力扣刷题笔记 #05-2 二维动态规划
https://hwcoder.top/LeetCode-DP-2
作者
Wei He
发布于
2022年10月2日
许可协议