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

️如何将问题抽象为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

得到的就是最后一块石头的重量。

状态定义：

表示从前

个元素中选择，不超过

的最大元素和，其中每个元素只能选择一次。

确定初始状态：

我们考虑当

时表示没有任何元素可以选择，所以不论

为何值时，

。

状态转移方程：

我们考虑选择第

个元素，重量为

，如果我们不选择该元素，

，如果我们选择该元素，前提必须满足

，此时

，由于是求最大值，所以选择两者更大的那一个。

所以最终状态转移方程为

。

实现代码：

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(n

sum/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(n

sum/2)

O(2

(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[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];
 }
}


时间复杂度：

空间复杂度：

练习：目标和

题目： 

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

，所以计算式的范围是

区间内的整数，一共

个。

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

状态定义：

定义

为前

个元素加权后构成计算式的值为

的方案数，

。

我们知道计算式的范围是

区间内的整数，由于数组的下标不能为负值，所以我们定义动态规划数组时需向右偏移

位，即

中的目标值

，那么

中的目标值为

，不难推出实际下标值为

。计算式的范围有

个整数，所以需要申请动态规划数组的列数为

。

确定初始状态：

当没有元素可以加权时，它的结果只能是

0

，所以只有当

j

为

0

时有一种方案，其余情况均没有方案，我们考虑这种情况为初始状态，则

，

时

。

状态转移方程：

所谓对数组元素加权

+/-

其实就是决定该元素是被加还是被减，我们来考虑第

i

个元素，假设该元素的值为

t

，如果选择加，则方案数为

，前提是

，如果选择减，则方案数为

，前提是$j+s+t<=2

s

j+s-t<0

j+s+t>2

s

0$。

状态转移方程为

。

实现代码：

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(2

len

s)

O(2

len

s)$

滚动数组优化：

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(2

len

s)

O(4*s)$

由于当行的数据更新，与前一行的前后都有关系，因此对于这道题不适合一维优化，但是我们定义状态时，考虑了

区间内所有的值，这就包含了目标情况不可能取到的一些状态值。下面我们根据这一点来进行优化。

优化方案

比如当题目给的

不为

和

时，那这两个值就是无效的状态值。为了规避掉这些无效的状态值，我们重新开始再来分析分析，我们将赋予

权重的分为一组叫做【正权重部分】,反之将赋予

的分为一组叫做【负权重部分】，不妨设数组的绝对值元素和为

，【负权重部分】的绝对值元素和为

，则【正权重部分】的元素和为

，我们可以做以下的推导。由题意得到，目标值

为【正权重部分】的计算值减去【负权重部分】的计算值（绝对值）。

根据推断，只要凑出

，那么【正权重部分】也就确定了，于是问题就变成仅使用

，从数组中凑出

的方案数，但是前提是

能够被

整除，如果不能被

整除，表示无法凑出

，方案数直接为

，所以需要在

为偶数的情况下，才会存在有效的方案。

在原问题中的

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

状态定义：

表示从数组前

个元素中选择（每个元素只能被选择一次）,凑出的元素和恰好为

的方案数。

确定初始状态：

当没有任何元素可以选择时，显然除了

其余的均没有方案。

状态转移方程：

对于第

个元素，值为

，如果不选，则方案数为

，如果选择，则方案数

，总方案数

。

实现代码：

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];
 }
}


时间复杂度：

空间复杂度：

滚动数组优化：

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];
 }
}


时间复杂度：

空间复杂度：

一维数组优化：

我们根据状态转移方程可以发现当行的

只与前一行

与

有关，所以

更新要比

在前，且

，所以一维优化时需从后往前遍历，

最小取值为

，保证

。

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];
 }
}


时间复杂度：

空间复杂度：

参考资料：

宫水三叶背包问题