动态规划之如何将问题抽象转化为 0-1 背包问题（详解利用动态规划求方案数）

作者：未见花闻

2022 年 6 月 12 日
本文字数：7635 字
阅读完需：约 25 分钟

⭐️如何将问题抽象为 0-1 背包⭐️

通过一道题来说明如何将问题抽象为 0-1 背包问题。

🔐最后一块石头的重量 II

题目：1049. 最后一块石头的重量 II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：

输入：stones = [2,7,4,1,8,1]输出：1解释：组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

复制代码

示例 2：

输入：stones = [31,26,33,21,40]输出：5

复制代码

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 100

💡解题思路

分析：

题目告诉了我们每个石头的重量，两块石头粉碎后，只会剩下正差值的重量的石头，该石头可能会再次参与粉碎操作，题目要求的是一堆石头经过很多次两两粉碎后，剩余最后一块的最小重量。

两块石头进行“粉碎时”可以将重量较大的石头分为一组，称为大堆，粉碎时，相当于给大堆的石块赋予+权重，将重量较小的石头分为一组，称为小堆，给小堆的石块赋予-权重，当我们不考虑粉碎后的石头放回的情况时，本质上就是计算赋予+或-得到的计算式子的值。

如果考虑粉碎石头重新放回的情况，其实本质上就是将原来分好的石块进行重组，比如假如有两个石块重量分别为a, b，满足a>=b，则粉碎后新石头的重量为a-b，不妨将这块新得到的石头称为“粉碎重生石”，该石头遇到一个比自身重量大的石头，重量为c，再次粉碎后，重量为c-(a-b)，我们发现相比于原来的式子，只是a的权重变为-，b的权重变为+，也就是发生了两个石头的权重发生了交换，同理，“粉碎重生石”遇到比自身重量小的石头，重量为d，则粉碎后重量变为(a-b)-d，a，b的权重不改变。虽然a,b的权重发生了改变，即对于大堆里面的单块石头不一定会比小堆里面的单块石头重，但是大堆的重量和依然会大于小堆的重量和。由于大堆里面的石头重量权重全部是+，小堆里面的石头权重全部为-，所以不妨将大堆称为+权重堆，小堆称为-权重堆。

综上分析，石头经历多次粉碎，改变的仅仅只是分布在哪一个组里面而已，只不过组的分界条件，由两块石头哪块更重变为最终石头被赋予的权重是+还是-，所以本质上就是给石堆重量数组中的元素添加+/-号，得到一个计算表达式，然后去求这个表达式的值，满足最接近0并不小于0的那个表达式的值就是我们所要的答案，也就是最后一块石头的重量。

那么此时，问题不知不觉就转化为：给你一堆石头的重量，每个石头只能选择一次，每次你可以加这个石头的重量，也可以减石头的重量，求不小于 0 的最小重量。

那这不就和之前做的[分割等和子集]那道题很像吗？我们把被赋予+权重的石头分为一组，被赋予-权重的石头分为一组，这两组就相当于数组的两个子集，求两个子集的最小差值。

不妨设+权重堆的总重量为big_sum，不妨设-权重堆的总重量为small_sum，那差值重量就是big_sum-small_sum的绝对值。假设石堆的总重量为sum，则sum=big_sum+small_sum，经过上述分析big_sum>=small_sum。

不难推出small_sum<=sum/2，即此时问题变为从石堆重量数组中选择若干元素，求不超过sum/2的最大元素和，这就完完全全的 0-1 背包问题了。

最后再拿这个最大和的两倍减去sum得到的就是最后一块石头的重量。

状态定义：

$d p [i] [j]$ 表示从前 $i$ 个元素中选择，不超过 $j$ 的最大元素和，其中每个元素只能选择一次。

确定初始状态：

我们考虑当 $i = 0$ 时表示没有任何元素可以选择，所以不论 $j$ 为何值时， $d p [i] [j] = 0$ 。

状态转移方程：

我们考虑选择第 $i$ 个元素，重量为 $s t o n e s [i - 1]$ ，如果我们不选择该元素， $d p [i] [j] = d p [i - 1] [j]$ ，如果我们选择该元素，前提必须满足 $j > = s t o n e s [i - 1]$ ，此时 $d p [i] [j] = d p [i - 1] [j - s t o n e s [i - 1]]$ ，由于是求最大值，所以选择两者更大的那一个。

所以最终状态转移方程为 $d p [i] [j] = m a x (d p [i - 1] [j], d p [i - 1] [j - s t o n e s [i - 1]])$ 。

实现代码：

class Solution {    public int lastStoneWeightII(int[] stones) {        int sum = 0;        for (int x : stones) {            sum += x;        }        int ret = sum / 2;        int n = stones.length;        int[][] dp = new int[n+1][ret+1];        for (int i = 1; i <= n; i++) {            for (int j = 0; j <= ret; j++) {                int x = dp[i-1][j];                int y = j >= stones[i-1] ? dp[i-1][j-stones[i-1]] + stones[i-1] : 0;                dp[i][j] = Math.max(x, y);            }        }        return sum - 2 * dp[n][ret];    }}

复制代码

时间复杂度：$O(nsum/2) $空间复杂度：$ O((n+1)(sum/2+1))$

滚动数组优化：

class Solution {    public int lastStoneWeightII(int[] stones) {        int sum = 0;        for (int x : stones) {            sum += x;        }        int ret = sum / 2;        int n = stones.length;        int[][] dp = new int[2][ret+1];
        for (int i = 1; i <= n; i++) {            for (int j = 0; j <= ret; j++) {                int index = (i-1) & 1;                int x = dp[index][j];                int y = j >= stones[i-1] ? dp[index][j-stones[i-1]] + stones[i-1] : 0;                dp[i&1][j] = Math.max(x, y);            }        }        return sum - 2 * dp[n&1][ret];    }}

复制代码

时间复杂度：$O(nsum/2) $空间复杂度：$ O(2(sum/2+1))$一维数组优化： $d p [j]$ 仅依赖上一行的 $d p [j]$ 与 $d p [j - s t o n e s [i - 1]]$ ，更新第 $j$ 列的值时 $j - s t o n e s [i - 1]$ 列的值必须还是未更新的值，所以采取从后往前遍历的方式，为了保证 $j > = s t o n e s [i - 1]$ ， $j$ 的最小取值为 $s t o n e s [i - 1]$ 。

class Solution {    public int lastStoneWeightII(int[] stones) {        int sum = 0;        for (int x : stones) {            sum += x;        }        int ret = sum / 2;        int n = stones.length;        int[] dp = new int[ret+1];        for (int i = 1; i <= n; i++) {            for (int j = ret; j >= stones[i-1]; j--) {                int x = stones[i-1];                dp[j] = Math.max(dp[j], dp[j-x]+x);            }        }        return sum - 2 * dp[ret];    }}

复制代码

时间复杂度： $O (n * (s u m / 2 - s t o n e s [i - 1]))$ 空间复杂度： $O (s u m / 2 + 1)$

📝练习：目标和

题目： 494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3输出：5解释：一共有 5 种方法让最终目标和为 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+1 + 1 + 1 + 1 - 1 = 3

复制代码

示例 2：

输入：nums = [1], target = 1输出：1

复制代码

提示：

1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000

🔑习题解答

分析：

这道题就是给数组nums的元素添加+/-权重，使得计算式的值为target，与上面【最后一块石头的重量 II】的区别就是前者求计算式结果不小于0的最小值，这里是求计算式的结果为target的方案数，本质上还是一共 0-背包问题，只不过价值与物品空间的对应关系发生了改变而已，即每个物品的价值均为1。

我们先来考虑计算式的极限边界，不妨设数组nums的元素绝对值的和为s，当权重全部为-时，计算式的结果为-s，当权重全部为+时，计算式结果为s，所以计算式的范围是 $[- s, s]$ 区间内的整数，一共 $2 * s + 1$ 个。

然后我们来考虑定义状态的定义。

状态定义：定义 $d p [i] [j]$ 为前 $i$ 个元素加权后构成计算式的值为 $j$ 的方案数， $- s < = j < = s$ 。

我们知道计算式的范围是 $[- s, s]$ 区间内的整数，由于数组的下标不能为负值，所以我们定义动态规划数组时需向右偏移 $s$ 位，即 $d p [i] [0]$ 中的目标值 $j = - s$ ，那么 $d p [i] [s]$ 中的目标值为 $j = 0$ ，不难推出实际下标值为 $j + s$ 。计算式的范围有 $2 s + 1$ 个整数，所以需要申请动态规划数组的列数为 $2 * s + 1$ 。

确定初始状态：

当没有元素可以加权时，它的结果只能是0，所以只有当j为0时有一种方案，其余情况均没有方案，我们考虑这种情况为初始状态，则 $d p [0] [s] = 1$ ， $j > = 1$ 时 $d p [0] [j + s] = 0$ 。

状态转移方程：

所谓对数组元素加权+/-其实就是决定该元素是被加还是被减，我们来考虑第i个元素，假设该元素的值为t，如果选择加，则方案数为 $d p [i - 1] [j + s - t]$ ，前提是 $j + s - t > = 0$ ，如果选择减，则方案数为 $d p [i - 1] [j + s + t]$ ，前提是 $j+s+t<=2s $。此时的方案数为满足上述两种情况方案数之和，如果$ j+s-t<0 $或$ j+s+t>2s $，则对应的方案数就是$ 0$。

状态转移方程为 $d p [i] [j] = d p [i - 1] [j + s - t] + d [i - 1] [j + s + t]$ 。

实现代码：

class Solution {    public int findTargetSumWays(int[] nums, int target) {        //动态规划        //状态转移方程dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]]        //i表示数组前i个元素，j表示目标和，dp[i][j]表示从前i个元素中进行+/-得到j的方案数        //考虑极端情况，目标和最大取值为数组的元素绝对值之和记为s，最小值为-s,所以j的可能取值一共2s+1个
        //1. 求数组元素绝对值的和        int s = 0;        for (int x : nums) {            s += Math.abs(x);        }        //如果target绝对值大于数组目标和的最大值，不可能存在合法的方案        if (Math.abs(target) > s) {            return 0;        }        //2. 创建动态规划数组        int len = nums.length;        int[][] dp = new int[len + 1][2 *s + 1];
        //3. 初始化,0->-s,s->0        dp[0][s] = 1;
        //4. 处理剩余情况        for (int i = 1; i <= len; i++) {            int t = nums[i - 1];            for (int j = -s; j <= s; j++) {                //当权重为+时，如果满足合法范围,加上dp[i - 1][j + s - t]                if (j + s - t >= 0) {                    dp[i][j + s] += dp[i - 1][j + s - t];                }                //当权重为-时，如果满足合法范围,加上dp[i - 1][j + s + t]                if (j + s + t <= 2 * s) {                    dp[i][j + s] += dp[i - 1][j + s + t];                }            }        }        return dp[len][target+s];    }}

复制代码

时间复杂度：$O(2lens) $空间复杂度：$ O(2lens)$

滚动数组优化：

class Solution {    public int findTargetSumWays(int[] nums, int target) {        //动态规划        //状态转移方程dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]]        //i表示数组前i个元素，j表示目标和，dp[i][j]表示从前i个元素中进行+/-得到j的方案数        //考虑极端情况，目标和最大取值为数组的元素绝对值之和记为s，最小值为-s,所以j的可能取值一共2s+1个
        //1. 求数组元素绝对值的和        int s = 0;        for (int x : nums) {            s += Math.abs(x);        }        //如果target绝对值大于数组目标和的最大值，不可能存在合法的方案        if (Math.abs(target) > s) {            return 0;        }        //2. 创建动态规划数组        int len = nums.length;        int[][] dp = new int[2][2 *s + 1];
        //3. 初始化,0->-s,s->0        dp[0][s] = 1;
        //4. 处理剩余情况        for (int i = 1; i <= len; i++) {            int t = nums[i - 1];            for (int j = -s; j <= s; j++) {                //更新值时，需要对原来那一行的值归零                dp[i&1][j + s] = 0;                                //如果满足左边界的值,加上dp[i - 1][j + s - t]                if (j + s - t >= 0) {                    dp[i&1][j + s] += dp[(i-1)&1][j + s - t];                }                //如果满足右边界的值，加上dp[i - 1][j + s + t]                if (j + s + t <= 2 * s) {                    dp[i&1][j + s] += dp[(i-1)&1][j + s + t];                }            }        }        return dp[len&1][target+s];    }}

复制代码

时间复杂度：$O(2lens) $空间复杂度：$ O(4*s)$

由于当行的数据更新，与前一行的前后都有关系，因此对于这道题不适合一维优化，但是我们定义状态时，考虑了 $[- s, s]$ 区间内所有的值，这就包含了目标情况不可能取到的一些状态值。下面我们根据这一点来进行优化。

✨优化方案

比如当题目给的 $t a r g e t$ 不为 $s$ 和 $- s$ 时，那这两个值就是无效的状态值。为了规避掉这些无效的状态值，我们重新开始再来分析分析，我们将赋予 $+$ 权重的分为一组叫做【正权重部分】,反之将赋予 $-$ 的分为一组叫做【负权重部分】，不妨设数组的绝对值元素和为 $s$ ，【负权重部分】的绝对值元素和为 $m$ ，则【正权重部分】的元素和为 $s - m$ ，我们可以做以下的推导。由题意得到，目标值 $t a r g e t$ 为【正权重部分】的计算值减去【负权重部分】的计算值（绝对值）。

(s - m) - m = t a r g e t

s - 2 * m = t a r g e t

m = \frac{s - t a r g e t}{2}

根据推断，只要凑出 $m$ ，那么【正权重部分】也就确定了，于是问题就变成仅使用 $+$ ，从数组中凑出 $m$ 的方案数，但是前提是 $s - t a r g e t$ 能够被 $2$ 整除，如果不能被 $2$ 整除，表示无法凑出 $t a r g e t$ ，方案数直接为 $0$ ，所以需要在 $s - t a r g e t$ 为偶数的情况下，才会存在有效的方案。

在原问题中的 $m$ 会被赋予负权重，剩下的元素会被赋予正权重，由以上分析我们可以开始定义状态。

状态定义： $d p [i] [j]$ 表示从数组前 $i$ 个元素中选择（每个元素只能被选择一次）,凑出的元素和恰好为 $j$ 的方案数。确定初始状态：当没有任何元素可以选择时，显然除了 $d p [0] [0] = 1$ 其余的均没有方案。状态转移方程：对于第 $i$ 个元素，值为 $t$ ，如果不选，则方案数为 $d p [i - 1] [j]$ ，如果选择，则方案数 $d p [i - 1] [j - t]$ ，总方案数 $d p [i] [j] = d p [i - 1] [j] + d p [i - 1] [j - t]$ 。

实现代码：

class Solution {    public int findTargetSumWays(int[] nums, int target) {        //动态规划        //对于第i个元素，值为t，如果不选，则方案数dp[i-1][j]，如果选择，则方案数dp[i-1][j-t]，总方案数dp[i][j]=dp[i-1][j]+dp[i-1][j-t]。
        //1. 求数组元素绝对值的和        int s = 0;        for (int x : nums) {            s += Math.abs(x);        }        int m = (s - target) / 2;        //如果target绝对值大于数组目标和的最大值，或者s-target不是偶数，不可能存在合法的方案        if (Math.abs(target) > s || (s - target) % 2 != 0) {            return 0;        }        //2. 创建动态规划数组,一维优化        int len = nums.length;        int[][] dp = new int[len+1][m+1];
        //3. 初始化dp[0][0] = 1;        dp[0][0] = 1;
        //4. 处理剩余情况        for (int i = 1; i <= len; i++) {            int t = nums[i - 1];            for (int j = 0; j <= m; j++) {                dp[i][j] = dp[i-1][j];                if (j >= t) {                    dp[i][j] += dp[i-1][j-t];                }            }        }        return dp[len][m];    }}

复制代码

时间复杂度： $O (l e n * (s - t a r g e t))$ 空间复杂度： $O (l e n * (s - t a r g e t))$

滚动数组优化：

class Solution {    public int findTargetSumWays(int[] nums, int target) {        //动态规划        //对于第i个元素，值为t，如果不选，则方案数dp[i-1][j]，如果选择，则方案数dp[i-1][j-t]，总方案数dp[i][j]=dp[i-1][j]+dp[i-1][j-t]。
        //1. 求数组元素绝对值的和        int s = 0;        for (int x : nums) {            s += Math.abs(x);        }        int m = (s - target) / 2;        //如果target绝对值大于数组目标和的最大值，或者s-target不是偶数，不可能存在合法的方案        if (Math.abs(target) > s || (s - target) % 2 != 0) {            return 0;        }        //2. 创建动态规划数组,一维优化        int len = nums.length;        int[][] dp = new int[2][m+1];
        //3. 初始化dp[0][0] = 1;        dp[0][0] = 1;
        //4. 处理剩余情况        for (int i = 1; i <= len; i++) {            int t = nums[i - 1];            for (int j = 0; j <= m; j++) {                dp[i&1][j] = dp[(i-1)&1][j];                if (j >= t) {                    dp[i&1][j] += dp[(i-1)&1][j-t];                }            }        }        return dp[len&1][m];    }}

复制代码

时间复杂度： $O (l e n * (s - t a r g e t))$ 空间复杂度： $O (2 * (s - t a r g e t))$ 一维数组优化：我们根据状态转移方程可以发现当行的 $d p [j]$ 只与前一行 $d p [j]$ 与 $d p [j - t]$ 有关，所以 $d p [j]$ 更新要比 $d p [j - t]$ 在前，且 $j > j - t$ ，所以一维优化时需从后往前遍历， $j$ 最小取值为 $t$ ，保证 $j > = t$ 。

class Solution {    public int findTargetSumWays(int[] nums, int target) {        //动态规划        //对于第i个元素，值为t，如果不选，则方案数dp[i-1][j]，如果选择，则方案数dp[i-1][j-t]，总方案数dp[i][j]=dp[i-1][j]+dp[i-1][j-t]。
        //1. 求数组元素绝对值的和        int s = 0;        for (int x : nums) {            s += Math.abs(x);        }        int m = (s - target) / 2;        //如果target绝对值大于数组目标和的最大值，或者s-target不是偶数，不可能存在合法的方案        if (Math.abs(target) > s || (s - target) % 2 != 0) {            return 0;        }        //2. 创建动态规划数组,一维优化        int len = nums.length;        int[] dp = new int[m+1];
        //3. 初始化dp[0] = 1;        dp[0] = 1;
        //4. 处理剩余情况        for (int i = 1; i <= len; i++) {            int t = nums[i - 1];            for (int j = m; j >= t; j--) {                dp[j] += dp[j-t];            }        }        return dp[m];    }}