算法萌新如何学好动态规划（3）

本文是「动态规划」系列文章的第三篇，作为算法萌新如何学好动态规划（2）的一个延伸。本篇文章将主要聚焦于动态规划经典模型 —— 背包问题的讲解。

背包问题属于线性 DP 模型，之所以单独拎出来讲，主要是因为该问题信息量大且十分重要，属于面试中常考且必会的知识，因此我们将其放在本系列的第三篇进行介绍。

本文一共分为三个部分，具体内容框架如下所示：

前文回顾

解题思路回顾

回顾动态规划系列的第一篇文章，动态规划解题过程一共分为两步，一是确定「DP 状态」，二是确定「DP 转移方程」。

「DP 状态」的确定有两大原则，一是「最优子结构」，二是「无后效性」，简要概括就是将原问题划分为多个子问题，且「大规模子问题最优值」仅与「小规模子问题最优值」有关，与「小规模子问题最优值」是如何得到的无关。
此处的「大规模」与「小规模」，就是「DP 问题」的关键所在，也是 DP 问题分类的重要标准。
确定完「DP 状态」后，只需要分类讨论、细心枚举各种情况，即可得到「DP 转移方程」。

大家在看本文时，一定要细心体会每一个经典背包模型的「DP 状态」与「DP 转移方程」，认真思考每一个模型中这两部分是如何得到的。学习不同经典模型，理解模型本质，才能不断加深对「动态规划」问题的理解。

线性 DP 特点回顾

线性划分 DP 规模的动态规划算法被统称为线性 DP。在线性 DP 中，DP 状态从「小规模」转移到「大规模」的同时，DP 状态沿着各个维度线性增长。

我们在动态规划系列的第二篇文章中介绍了三个常见的线性 DP 模型，分别是「最长上升子序列 LIS」、「最长公共子序列 LCS」以及「数字三角形」，其特点如下图所示。

本文将介绍第四个线性 DP 模型，即「背包问题」。由于背包问题也是线性 DP 问题，因此也符合线性 DP 的特点，即 DP 状态沿着各个维度线性增长，大家可以在下文中着重关注一下这一特点。

背包问题概述

常见的背包问题一共有三类，分别是「0/1 背包」、「完全背包」以及「多重背包」，接下来我们将依次进行介绍。

0/1 背包

0/1 背包的基本模型如下所示：

一共有 N 个物品，其中第 i 个物品的体积为

，价值为

。现要求选择一些物品放入一个容积为 M 的背包中，使得物品总体积不超过 M 的前提下，物品总价值最大。

现在我们来思考下如何根据线性 DP 的知识来解决这个问题。

线性 DP 的特点是 DP 状态沿着各个维度线性增长。而本问题中只有三个参数，分别是物品编号、物品体积以及物品价值。由于我们要求的是物品总价值最大，因此不难想到令 DP 状态为

，表示仅考虑前 i 个物品，所选物品总体积为 j 时的最大物品总价值。

确定「DP 状态」后，我们来考虑「DP 转移方程」是什么。

对于第 i 个物品来说，它只有两种状态，即要么取，要么不取。如果不取第 i 个物品，则

；如果取第 i 个物品，则

，因此我们得到如下「DP 转移方程」：

其中初值

为负无穷，其中

，最终答案为

，代码如下所示。

intDP() {for(int i = 1; i <= M; i++) f[0][j] = -inf; // 负无穷，inf 可以为 1e8 f[0][0] = 0;for(int i = 1; i <= N; i++)for(int j = 0; j <= M; j++)if(j >= v[i]) f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i]);else f[i][j] = f[i-1][j];int ans = 0;for(int i = 0; i <= M; i++) ans = max(ans, f[N][i]);return ans;}

观察上述代码，不难发现，

仅由

和

决定。这就给了我们一个思考角度，即能否将二维数组 f 的第一维去掉？

答案显然是可以的，我们可以倒序枚举 j，使得更新

时

还未被更新，即

代表的实际是

的值。这样说可能不好理解，我们先看一下优化后的代码：

intDP() {for(int i = 1; i <= M; i++) f[j] = -inf; // 负无穷，inf 可以为 1e8 f[0] = 0;for(int i = 1; i <= N; i++)for(int j = M; j >= v[i]; j++) f[j] = max(f[j], f[j-v[i]] + w[i]);int ans = 0;for(int i = 0; i <= M; i++) ans = max(ans, f[i]);return ans;}

根据上述代码，我们不难发现在第 i 轮，更新到

时，

与

代表的都是第 i - 1 轮的值，即

与

。而在我们更新完

后，

的值即变为

的值，由此我们大大降低了该算法的空间开销，这种空间优化方法叫做「滚动数组」。

完全背包

了解完「0/1 背包」模型后，我们继续介绍「完全背包」模型，其基本问题如下所示：

一共有 N 类物品，其中第 i 类物品的体积为

，价值为

，且每类物品可以选无数个。现要求选择一些物品放入一个容积为 M 的背包中，使得物品总体积不超过 M 的前提下，物品总价值最大。

不难发现，「完全背包」与「0/1 背包」最大的差别就在于每一类物品可以选多少个，其中「完全背包」每一类物品可以选无数个，而「0/1 背包」中每一类物品只能选 1 个。

了解完模型差异后，我们继续思考如何解决该问题。与「0/1 背包」模型比较类似，本问题也只有三个参数，分别是物品编号、物品体积以及物品价值。因此我们可以照搬「0/1 背包」的「DP 状态」，即

表示仅考虑前 i 类物品，所选物品总体积为 j 时的最大物品总价值。

由于每一类物品可以选无数次，因此对于

来说，如果不取则

，如果取一个则

，如果取两个则

，如果取 x 个则

。

因此我们可以得到

但这样的话我们就需要不断遍历 x，显然会导致时间复杂度过高，因此我们还可以继续优化。

又因为

因此只要正序遍历 j，即保证求取

时，

已经得到，「DP 转移方程」就可以优化为

对比「0/1 背包」中

，「完全背包」由于每类物品可以取多次，因此转移方程变为

，具体代码如下所示。

intDP() {for(int i = 1; i <= M; i++) f[0][j] = -inf; // 负无穷，inf 可以为 1e8 f[0][0] = 0;for(int i = 1; i <= N; i++)for(int j = 0; j <= M; j++)if(j >= v[i]) f[i][j] = max(f[i-1][j], f[i][j-v[i]] + w[i]);else f[i][j] = f[i-1][j];int ans = 0;for(int i = 0; i <= M; i++) ans = max(ans, f[N][i]);return ans;}

根据之前介绍的「滚动数组」方法，我们可以将上述代码优化为：

intDP() {for(int i = 1; i <= M; i++) f[j] = -inf; // 负无穷，inf 可以为 1e8 f[0] = 0;for(int i = 1; i <= N; i++)for(int j = v[i]; j <= M; j++) f[j] = max(f[j], f[j-v[i]] + w[i]);int ans = 0;for(int i = 0; i <= M; i++) ans = max(ans, f[i]);return ans;}

多重背包

最后我们来介绍「多重背包」模型，其基本问题如下所示：

一共有 N 类物品，其中第 i 类物品的体积为

，价值为

，且每类物品只有

个

。现要求选择一些物品放入一个容积为 M 的背包中，使得物品总体积不超过 M 的前提下，物品总价值最大。

将该问题与「0/1 背包」模型进行对比，可以发现唯一差别在于「0/1 背包」中每一类物品的

，因此我们可以考虑如何将「多重背包」转换为「0/1 背包」进行求解。

首先比较容易想到的是，我们可以进行暴力拆分，即将每一类物品拆分为

个，总物品数量从 N 变为

，因此我们可以直接使用「0/1 背包」模型进行解决，具体代码如下所示：

intDP() {for(int i = 1; i <= M; i++) f[j] = -inf; // 负无穷，inf 可以为 1e8 f[0] = 0;for(int i = 1; i <= N; i++)for(int k = 1; k <= c[i]; k++)for(int j = M; j >= v[i]; j++) f[j] = max(f[j], f[j-v[i]] + w[i]);int ans = 0;for(int i = 0; i <= M; i++) ans = max(ans, f[i]);return ans;}

直接暴力拆分使得该问题变得简单，但是时间复杂度却显著增加，为

。于是我们需要思考有没有什么方法可以对该问题进行优化？

答案显然是有的，即对每一类物品进行二进制拆分。首先回顾计算机中二进制的知识，即从

这 k 个数字中选取若干个相加，可以表示出

中的任何整数。

因此对于第 i 类物品，其个数为

，我们可以求出满足

的最大的 p，并令

。

因为 p 是最大的，所以

，即

。又因为

的最大表示范围为

，因此我们可以从

中选取若干个数表示出

中的任何整数。

又因为

，因此我们可以使用

以及

表示出

中的任何整数。

所以

，

的表示范围恰好为

，即我们可以将数量为

的第 i 类物品拆分为 p + 2 个物品，其体积分别为：

其价值分别为：

拆分完每一类物品后，我们再使用「0/1 背包」模型即可求出答案，总时间复杂度为

。

背包问题特点

至此我们介绍完了三大常见的背包模型，分别是「0/1 背包」、「完全背包」、「多重背包」，其区别仅仅在于每一类物品可以选多少个。其中「0/1 背包」是每一类物品只能选一个，「完全背包」则是每一类物品可以选无数个，而「多重背包」则是第 i 类物品最多可以选

个。

因此我们可以归纳「背包问题」的特点：有 N 类物品，每类物品可以选 1 个、无数个或

个，问是否存在一种选取方案，使其满足某种条件。或者是否存在一种选取方案，使其满足某种条件的同时，得到某种参数的最值。

这样归纳可能还是过于抽象，因此我们将在下文「习题练习」中讲解一些具体的题型来帮助大家理解。

习题练习

416. 分割等和子集

题目描述

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1

输入: [1, 5, 11, 5]输出: true解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2

输入: [1, 2, 3, 5]输出: false解释: 数组不能分割成两个元素和相等的子集.

提示

每个数组中的元素不会超过 100
数组的大小不会超过 200

解题思路

「将数组分割成两个子集，使得两个子集的元素和相等」，假设数组元素个数为N，元素和为 M，则问题可以转化为「现有 N 个数字，是否可以选取若干个数字，使其和为 M/2」。

进行这一步转换之后，则可以较为明显的看出该问题本质上是从 N 物品中选取若干个物品，即「背包问题」。并且每个物品只能选一次，因此是「0/1 背包」模型。

仿照「0/1 背包」模型，我们可以定义

为仅考虑前 i 个物品，是否存在一种选择方案使其数值和为 j。我们规定若

则表示存在一种方案；若

则表示不存在可行方案。

因此我们可以得到如下「DP 转移方程」：

定义一下初始条件，

。接下来直接套用「0/1 背包」滚动数组版本的代码即可完成本题，具体细节见下述代码。

C++ 代码实现

classSolution {public:vector<int> f;boolcanPartition(vector<int>& nums){// 确保元素和为偶数int sum = 0;for(int item:nums) sum += item;if(sum % 2 != 0) return0; sum /= 2;// 开辟存储空间 f.resize(sum+1); f[0] = 1;// DP 过程for(int i = 1; i <= nums.size(); i++)for(int j = sum; j >= nums[i-1]; j--)if(f[j-nums[i-1]] == 1) f[j] = 1;if(f[sum]) return1;elsereturn0; }};

494. 目标和

题目描述

给定一个非负整数数组，

和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 - 中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例

输入：nums: [1, 1, 1, 1, 1], S: 3输出：5解释： -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3一共有5种方法让最终目标和为3。

提示

数组非空，且长度不会超过 20 。
初始的数组的和不会超过 1000 。
保证返回的最终结果能被 32 位整数存下。

解题思路

假设整个数组元素和为 sum，且开头符号为 + 的数字和为 a，则整个开头符号为 - 的数字和为 sum - a。因此若要使数组和为 S，则 a - (sum - a) = S，即 2*a = S + sum。

因此问题转变为从 N 个数中选取若干个数，使其总和为

，问有多少种选数方案。

由于每个数只能选一次，因此我们可以较为容易地将该问题转化为「0/1 背包」模型。仿照「0/1 背包」，定义

表示仅考虑前 i 个数，有多少种选数方案使其数字和为 j。

因此我们可以得到如下「DP 转移方程」：

定义一下初始条件，

。接下来直接套用「0/1 背包」滚动数组版本的代码即可，具体细节见下述代码。

C++ 代码实现

classSolution {public:vector<int> f;intfindTargetSumWays(vector<int>& nums, int S){// 预处理int sum = 0, a = 0;for(int item:nums) sum += item;if(S < -sum || S > sum || (sum + S) % 2) return0; a = (S + sum) / 2; f.resize(a + 1);// DP 过程 f[0] = 1;for(int i = 0; i < nums.size(); i++)for(int j = a; j >= nums[i]; j--) f[j] += f[j-nums[i]];return f[a]; }};

322. 零钱兑换

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 - 1。

示例 1

输入: coins = [1, 2, 5], amount = 11输出: 3 解释: 11 = 5 + 5 + 1

示例 2

输入: coins = [2], amount = 3输出: -1

提示

你可以认为每种硬币的数量是无限的。

解题思路

从 N 类硬币中选取若干个，使得选取硬币的总金额为 M，求最少所需的硬币个数。很明显这是一道「背包类」问题，且由于每一类硬币可以选取无限个，因此这是一道「完全背包」问题。

仿照「完全背包」的思路，定义

表示仅考虑前 i 类硬币，其总金额为 j 时最少所需硬币个数。

因此我们可以得到如下「DP 转移方程」：

定义一下初始条件，

。接下来直接套用「完全背包」滚动数组版本的代码即可，具体细节见下述代码。

C++ 代码实现

classSolution {public:vector<int> f;constint inf = 1e8;intcoinChange(vector<int>& coins, int amount){ f.resize(amount + 1, inf); f[0] = 0;for(int i = 0; i < coins.size(); i++)for(int j = coins[i]; j <= amount; j++) f[j] = min(f[j], f[j-coins[i]] + 1);if(f[amount] == inf) return-1;elsereturn f[amount]; }};

518. 零钱兑换 II

题目描述

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1

输入: amount = 5, coins = [1, 2, 5]输出: 4解释: 有四种方式可以凑成总金额:5=55=2+2+15=2+1+1+15=1+1+1+1+1

示例 2

输入: amount = 3, coins = [2]输出: 0解释: 只用面额2的硬币不能凑成总金额3。

示例 3

输入: amount = 10, coins = [10] 输出: 1

提示

解题思路

本题与上一题唯一的区别在于，上一题要求的「凑成总金额最少需要的硬币个数」，而本题求的是「凑成总金额的方案数」。因此只需稍微改动一下「DP 状态意义」以及「DP 转移方程」即可。

由于本题的硬币依然可以无限取，因此仍然使用「完全背包」模型进行求解。定义

表示仅考虑前 i 类硬币，其总金额为 j 时的组合数。因此可以得到如下「DP 转移方程」：

初始条件为，

。接下来使用「完全背包」滚动数组版本的代码即可，具体细节如下。

C++ 代码实现

classSolution {public:vector<int> f;intchange(int amount, vector<int>& coins){ f.resize(amount + 1); f[0] = 1;for(int i = 0; i < coins.size(); i++)for(int j = coins[i]; j <= amount; j++) f[j] += f[j-coins[i]];return f[amount]; }};

474. 一和零

题目描述

在计算机界中，我们总是追求用有限的资源获取最大的收益。

现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。

你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。

示例 1

输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3输出: 4解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0"。

示例 2

输入: Array = {"10", "0", "1"}, m = 1, n = 1输出: 2解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1"。

提示

给定 0 和 1 的数量都不会超过 100。
给定字符串数组的长度不会超过 600。

解题思路

简要概括一下题意，一共有 m 个 0，n 个 1。现有 n 个字符串，其中第 i 个字符串需要

个 0，

个 1，现问最多可以拼出多少个字符串。

这个题看似可能和背包没太大关系，但仔细思考之后，还是可以发现此题的本质仍然是选取若干个字符串，使其 0 和 1 的个数之和分别小于等于 m 和 n，因此仍然是一道背包问题。并且由于每一个字符串只能选一次，因此是一道「0/1 背包」问题。

我们仿照「0/1 背包」的思路，定义

表示对于前 i 个字符串，一共有 j 个 0 和 k 个 1 时，能拼出的最大字符串个数。

可以发现对比「0/1 背包」的基础模型，我们将「DP 状态」从二维扩展到了三维，主要原因在于本题有两个参数，分别是 0 和 1 的个数。可以理解为有两个背包，要装两种东西，但本质不变，只需在原先基础上扩展一维即可。

因此我们可以仿照原先的基础模型，得到如下「DP 转移方程」：

初始条件为

。由于本题只是在「0/1 背包」模型基础上扩展了一维，因此我们仍然可以使用「滚动数组」的方法将三维空间降低至二维空间，具体代码如下所示。

C++ 代码实现

classSolution {public:vector<vector<int> > f;intfindMaxForm(vector<string>& strs, int m, int n){ f.resize(m+1);for(int i = 0; i <= m; i++) f[i].resize(n+1);for(int i = 0; i < strs.size(); i++) {int a = 0, b = 0;for(char c:strs[i]) {if(c == '0') a++;else b++; }for(int j = m; j >= a; j--)for(int k = n; k >= b; k--) f[j][k] = max(f[j][k], f[j-a][k-b] + 1); }return f[m][n]; }};

总结

讲解完上述五道例题后，我们可以发现「背包问题」的核心难点在于识别出这是一道「背包问题」。识别出是「背包问题」后，我们只需要观察每一个物品最多能取的次数，然后对应到具体的「0/1 背包」、「完全背包」、「多重背包」模型上即可推出对应的「DP 状态」以及「DP 转移方程」。

为了方便大家后续查阅，现将上述三个背包模型总结如下：

最后，希望大家能将本文的内容与算法萌新如何学好动态规划（2）中所讲解的「线性 DP」进行统一记忆与理解，在之后遇到「线性 DP」问题时可以参考这四类基础模型（LIS、LCS、数字三角形、背包），实现更快速地解题！

BY /

本文作者：Gene_Liu

编辑&版式：霍霍