【进击的算法】动态规划——不同维度的背包问题

前言

大家好久不见，这次我们一起来学习一下动态规划中怎么确定维度，和对应问题如何解决。

动态规划的维度

一个维度：只有物品
两个维度：物品和容量
三个维度：物品和容量1和容量2

之前讲解动态规划问题时，斐波那契数列就是一个很简单的一维动态规划问题，因为我们要考虑的状态只有这个数的值，（一维动态规划），之后讲解了01背包问题，也就是有了第二个维度，不仅要考虑物品，还要考虑背包容量（二维动态规划）

其实在这里一定要明确好状态到底是什么，在我看来：与要求结果相关的状态，都是可以列为维度的，我们是将物品范围和背包容量都列为了状态因为他们都会影响结果

---

二维动规

leetcode416、分割等和子集

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

• 示例 1：
  输入：nums = [1,5,11,5]
  输出：true
  解释：数组可以分割成 [1, 5, 5] 和 [11] 。
• 示例 2：
  输入：nums = [1,2,3,5]
  输出：false
  解释：数组不能分割成两个元素和相等的子集。

这个问题要我们寻找等和的子集，我们可以把nums数组里的元素抽象为背包问题里的石头，把分成的两个等和子集抽象为背包。

• dp[i][j] 表示前i个元素放到容量为j的背包的最大重量！

• dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i])

就算压缩为一维动态规划，那也是压缩的空间而已，本质上我们还是定义了两个状态！

#define MAX(a,b) ((a)>(b)?(a):(b))bool canPartition(int* nums, int numsSize){int sum = 0;for(int i = 0;i<numsSize;i++){sum+=nums[i];}if(sum%2 != 0) return false;int target = sum / 2;int* dp = (int*)calloc(sizeof(int),target+1);//先遍历物品，再遍历列！for(int i = 0;i<numsSize;i++){for(int j = target;j>=nums[i];j--){dp[j] = MAX(dp[j],dp[j-nums[i]]+nums[i]);}} if(dp[target] == target) return true;return false;
}

---

leetcode1049. 最后一块石头的重量 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]，这就是最优值。

这道题目，我们要获得撞后剩下的最小质量，只需要将这堆石头尽可能分为两堆一样重量的石头，相互碰撞即可。
在这道题目里，nums数组里的元素是石块，总重量的一半即是背包容量，我们要尽可能填满这一半的石头。

• dp[i][j] ——前i个石块放入j的背包的最大重量。
• dp[i][j] = max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i])

优化思路也和01背包问题一样，即滚动数组压缩

参考代码：

#define MAX(a,b) ((a)>(b)?(a):(b))
int lastStoneWeightII(int* stones, int stonesSize){int sum = 0;for(int i = 0;i<stonesSize;i++){sum += stones[i];}int target = sum/2;int dp[1501] = {0};for(int i = 0;i<stonesSize;i++)//遍历物品{for(int j = target;j>=stones[i];j--){dp[j] = MAX(dp[j],dp[j-stones[i]]+stones[i]);}}return sum - dp[target] - dp[target];
}

---

leetcode494、目标和

给你一个整数数组 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

这道问题其实也是要我们分为两组，本质上nums数组里的元素就是石块，分组的大小仍然是背包大小。唯一不同的是我们dp数组在定义上变成了要求多少种方法

• dp[i][j] ——前i个元素放入容量为j的背包，有多少种方法？
• dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]; //可以放也可以不放两者加起来就是总方法数

class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {//分组背包问题,一组放+，一组放-，凑成targetint sum = 0;for(auto e : nums){sum+=e;}//left rightif(abs(target) > sum) return 0;if((target + sum)%2 == 1) return 0;int left = (target + sum)/2;vector<int> dp(left+1,0);dp[0] = 1;for(int i = 0;i<nums.size();i++){for(int j = left;j>=nums[i];j--){dp[j] += dp[j-nums[i]];}}return dp[left];}
};

三维动规

leetcode474. 一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：
输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} ，因此答案是 4 。
其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

说白话就是用j个0和k个1最多能凑成几个nums中的字符串

这道题可以将数组里的元素抽象为石头，0和1的数量抽象为背包容量，很显然现在有两个背包容量

• dp[i][j][k]——在前 i 个字符串中，使用 j 个 0 和 k 个 1的情况下最多可以得到的字符串数量。
• dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-num1][k-num0] + 1);
  其实就是要不要把这个字符串放进来，比一下大的就行

class Solution {
public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0//dp[i][j] 表示容量为ij的背包能装的最大重量！for(string str : strs){int onenum = 0,zeronum = 0;for(char c : str){if(c == '1')onenum++;elsezeronum++;}for(int i = m;i>=zeronum;i--){for(int j = n;j>=onenum;j--){dp[i][j] = max(dp[i][j],dp[i-zeronum][j-onenum]+1);}}}return dp[m][n];}
};

结语

到这里本篇文章就结束了，希望能对你学习动态规划有所帮助，我们下次见~