力扣刷题笔记 #05-2 二维动态规划
本文最后更新于：2025年3月13日 上午
本文包含「动态规划」类型题中的：二维线性 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)\)。 \[ dp[i][j]=dp[i-1][j] + dp[i][j-1] \] 方法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)\)。 \[ dp\left[ i \right] \left[ j \right] =\min \left( dp\left[ i-1 \right] \left[ j \right] ,\; dp\left[ i \right] \left[ j-1 \right] ,\; dp\left[ i-1 \right] \left[ j-1 \right] \right) +1 \] 方法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)\)。 \[ \left\{ \begin{array}{c} dp\left[ i+1 \right] \left[ j \right] +=\frac{dp\left[ i \right] \left[ j \right] -1}{2}\\ dp\left[ i+1 \right] \left[ j+1 \right] +=\frac{dp\left[ i \right] \left[ j \right] -1}{2}\\ \end{array} \right. \] 方法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)\)。 \[ dp\left[ i \right] \left[ j \right] =\max \left\{ dp\left[ i \right] \left[ j+1 \right] +now\times nums\left[ j+1 \right] ,\;\; dp\left[ i-1 \right] \left[ j \right] +now\times nums\left[ i-1 \right] \right\} \] 方法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\left[ i \right] \left[ j \right] =\frac{1}{4}\times \left( dp\left[ i-4 \right] \left[ j \right] +dp\left[ i-3 \right] \left[ j-1 \right] +dp\left[ i-2 \right] \left[ j-2 \right] +dp\left[ i-1 \right] \left[ j-3 \right] \right) \]
边界值 \(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)\)。 \[ dp[i][j][(num+\operatorname{grid}[i][j]) \;\%\; k]+=dp[i][j-1][num]+dp[i-1][j][num],\;\; num\in[0,k) \] 或者： \[ \begin{aligned} dp[i][j][num]=dp[i][j-1][((num-\mathrm{grid[}i][j])\;\%\;k+k)\;\%\;k] \\ +dp[i-1][j][((num-\mathrm{grid[}i][j])\;\%\;k+k)\;\%\;k] \end{aligned} \] 方法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)\)。 \[ \left\{\begin{array}{l} P(i, i)&=\,\,\text {true} \\ P(i, i+1)&=\,\,\left(S_i==S_{i+1}\right) \\ P(i, j)&=\,\,P(i+1, j-1) \wedge\left(S_i==S_j\right) \end{array}\right. \] > 在转移过程中，\(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)\)。
132. 分割回文串 II (H)
题目描述：给一个字符串 s，请你将 s 分割成若干回文串。返回符合要求的最少分割次数 。
方法1：二维 DP + 一维 DP，同上题，先得到 \(dp[i][j]\) 数组表示 \(s[i\cdots j]\) 是否为回文串（布尔值），再线性扫描字符串，用 \(res[j]\) 表示 \(s[0\cdots j]\) 最少可分回文串数量。两次操作的时间复杂度都是 \(O(n^2)\)。 \[ res[j]=\left\{ \begin{array}{c} 1 \,\,, & \mathrm{if} (dp[0][j]==true) \\ \min(res[i]+1) \,\,, &\mathrm{otherwise\; if} (dp[i+1][j]==true)\\ \end{array} \right. \]
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)\)。 \[ dp[i][j]=\left\{ \begin{array}{c} dp\left[ i-1 \right] \left[ j-1 \right] +1 \,\,, & \mathrm{if}\left( s\left[ i-1 \right] =s\left[ j-1 \right] \right) \,\,\\ \max \left( dp\left[ i \right] \left[ j-1 \right] , dp\left[ i-1 \right] \left[ j \right] \right) \,\,, &\mathrm{otherwise}\\ \end{array} \right. \] 方法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)\)。 \[ dp[i][j]=\left\{ \begin{array}{c} dp\left[ i-1 \right] \left[ j-1 \right] \,\,, & \mathrm{if}\left( s\left[ i-1 \right] =s\left[ j-1 \right] \right) \,\,\\ \min \left( dp\left[ i-1 \right] \left[ j-1 \right], \; dp\left[ i \right] \left[ j-1 \right] ,\; dp\left[ i-1 \right] \left[ j \right] \right)+1 \,\,, &\mathrm{otherwise}\\ \end{array} \right. \]
当新来的两个字符相等时，不会增加编辑距离，因此由左上角转移。当两个字符不相等时，有三种转移可能：
- 通过替换一个 \(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[i][j]=\begin{cases} \,\,\mathrm{if} \left( p[j]\ne \text{星号} \right) =\begin{cases} f[i-1][j-1],& \,\,\mathrm{matches} (s[i],p[j])\\ \mathrm{false},& \,\,\mathrm{otherwise}\\ \end{cases}\\ \,\,\mathrm{otherwise} =\begin{cases} f[i-1][j]\,\, \mathrm{or} \,\,f[i][j-2],& \,\,\mathrm{matches} (s[i],p[j-1])\\ f[i][j-2],& \,\,\mathrm{otherwise}\\ \end{cases}\\ \end{cases} \]
坑点：
- \(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\) 件物品放或不放。
\[ dp[i][j]=\max \{dp[i-1][j], \; dp[i-1][j-w[i]]+v[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)\)。 \[ dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]] \] 方法3：01 背包，记所有正数的和为 \(x\)，负数为 \(sum-x\)，要求 \(x-(sum-x)=target\)，则 \(x=(target+sum)/2\)。该值必定非负。提前特判奇数情况、\(target>sum\) 情况，剩下的就是求装满容量为 \(x\) 的背包，有几种方法。 \[ dp[j] = dp[j] + dp[j - nums[i]] \]
474. 一和零 (M)
题目描述：给定一组二进制字符串，从中选取一个子集，子集中最多有 m 个 0 和 n 个 1。求最大子集长度。
本题易混淆为多重背包问题，实际上每个物品还是只能选一次，还是 01 背包，只是背包的容量有两个维度。
方法：多维 01 背包，\(dp[i][j]\) 表示两种物品的容量分别为 \(i\) 和 \(j\) 时的最大子集，由于涉及高维，这里直接采用滚动数组节约空间，倒着递推。每个串的价值都是 \(1\)，转移方程如下。复杂度 \(O(mn)\)。 \[ dp[i][j]=\max \left( dp[i][j], dp[i-zeros][j-ones]+1 \right) \]
Todo 2518. 好分区的数目 (H)
题目描述：
方法1：
方法2：
方法3：
以下是完全背包问题，这类问题中「每种物品可以放无限多次」。这类问题中题目包含：
背景：共有 \(n\) 件物品，最大容量为 \(m\) 的背包。第 \(i\) 件物品的价值是 \(v[i]\)，重量为 \(w[i]\)。
状态：\(dp[i][j]\) 表示前 \(i\) 件物品以某种组合能够放进容量为 \(j\) 的背包的最大价值，考虑第 \(i\) 件物品放多少个。
\[ dp[i][j]=\max \{dp[i-1][j-k\times w[i]]+k\times v[i]\} \;\; 0\leqslant k\times w[i]\leqslant j \]
初始化：数组大小至少为 \(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\) 的组合数，本题的特点在于不凑满的背包是不合法的，因此初始化首行时要间隔，状态转移方程也要修改。 \[ dp[i][j] += dp[i - 1][j - k \times coins[i]], \;\; 0\leqslant k\times coins[i]\leqslant j \] 方法2：完全背包 + 滚动数组，注意要初始化 \(dp[0]=1\)，理解为没有硬币时也有一种组合，再开始考虑第一种。 \[ dp[j] += [j - coins[i]] \]
由于外层循环先遍历 \(coins\) 数组，在内层循环中，可以确保硬币面额在排列中的顺序，不会重复考虑一个组合。
322. 零钱兑换 (M)
题目描述：同上，但返回的是可以凑成总金额所需的最少的硬币个数，如果不存在则返回 \(-1\)。
方法1：完全背包。\(dp[i][j]\) 表示用前 \(i\) 种硬币凑成 \(j\) 的最少个数，本题由于转移方程用到了 \(\min\)，所以初始值应该设为 0x3f，只有间隔位置的元素可以凑成，且 \(dp[0][0]=0\)。但是由于总金额过大，该方法会超时。 \[ dp[i][j]=\min \left( dp[i][j], \;dp[i-1][j-k\times coins[i]]+k \right) \] 方法2：完全背包 + 滚动数组，注意要初始化 \(dp[0]=0\)，理解为没有硬币时也可以凑齐零元。 \[ dp[j]=\min \left( dp[j],\;dp[j-coins[i]]+1 \right) \]
TODO 377. 组合总和 IV (M)
题目描述：给定由不同整数组成的数组 nums 和一个目标数。从 nums 中找出总和为目标数的元素组合的个数。顺序不同序列被视为不同的组合。
方法1：完全背包。
方法2：
以下是多重背包问题，这类问题中「每种物品各有一个指定的次数上限」。这类问题中题目包含：
背景：共有 \(n\) 件物品，最大容量为 \(m\) 的背包。第 \(i\) 件物品的价值是 \(v[i]\)，重量为 \(w[i]\)，其最多可装 \(s[i]\) 件。
状态：\(dp[i][j]\) 表示前 \(i\) 件物品以某种组合能够放进容量为 \(j\) 的背包的最大价值，考虑第 \(i\) 件物品放多少个。
\[ dp[i][j]=\max \{dp[i-1][j-k\times w[i]]+k\times v[i]\}\;\;0\leqslant k\times w[i]\leqslant j,\; 0\leqslant k\leqslant s\left[ i \right] \]
初始化：数组大小至少为 \(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 | |