01背包理论基础
406、分割等和子集
力扣题目链接
题目描述
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200
示例 1:
- 输入: [1, 5, 11, 5]
- 输出: true
思路分析（动规五步曲）：
1.确定dp数组以及下标的含义
01背包中，dp[j] 表示： 容量为j的背包，所背的物品价值最大可以为dp[j]。
本题中每一个元素的数值既是重量，也是价值。
套到本题，dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]。
那么如果背包容量为target， dp[target]就是装满 背包之后的重量，所以 当 dp[target] == target 的时候，背包就装满了。
2.确定递推公式
01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。
所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
3.初始化dp数组
如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。
4.确定遍历顺序
如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历
我觉得这是最难想明白的，最重要的是想通滚动数组只有一层，所以要从后往前遍历，不然就多算了，就成完全背包了
// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}5.举例推导dp数组
code（1）:
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
// dp[i]中的i表示背包内总和
// 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
// 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
vector<int> dp(10001, 0);
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
// 也可以使用库函数一步求和
// int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 == 1) return false;
int target = sum / 2;
// 开始 01背包
for(int i = 0; i < nums.size(); i++) {
for(int j = target; j >= nums[i]; j--) { // 每一个元素一定是不可重复放入，所以从大到小遍历
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
// 集合中的元素正好可以凑成总和target
if (dp[target] == target) return true;
return false;
}
};code（2）：
其实，只要给数组排序，然后从小到大遍历，只要和为target就返回true
class Solution {
public:
bool canPartition(vector<int>& nums) {
sort(nums.begin(),nums.end());
int sum=0;
for(int num:nums)sum+=num;
if(sum%2==1)return false;
int target=sum/2;
int cur=0;
for(int num:nums){
cur+=num;
if(cur==target)return true;
}
return false;
}
};1049、最后一块石头的重量||
力扣题目链接
题目描述
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。
示例：
- 输入：[2,7,4,1,8,1]
- 输出：1
思路分析
只要想明白，其实是要把石堆尽可能的分为相近的两堆，也就是sum/2,分析到这里，就能发现跟上一题很相似了，只是最后的处理有一点点不同，return sum-dp[target]-dp[target]
code：
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
//尽可能分为两份等可能的
vector<int>dp(15001,0);
int sum=0;
for(int i:stones){
sum+=i;
}
int target=sum/2;
//dp物品和背包
for(int i=0;i<stones.size();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];
}
};494、目标和
力扣题目链接
题目描述：
给你一个非负整数数组
nums和一个整数target。向数组中的每个整数前添加
'+'或'-'，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，
nums = [2, 1]，可以在2之前添加'+'，在1之前添加'-'，然后串联起来得到表达式"+2-1"。返回可以通过上述方法构造的、运算结果等于
target的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。
思路分析（五步曲）：
救命，太强啦！！！怎么想到的啊
这道题目咋眼一看和动态规划背包啥的也没啥关系。
本题要如何使表达式结果为target，
既然为target，那么就一定有 left组合 - right组合 = target。
left + right = sum，而sum是固定的。right = sum - left
left - (sum - left) = target 推导出 left = (target + sum)/2 。
target是固定的，sum是固定的，left就可以求出来。
此时问题就是在集合nums中找出和为left的组合。
注意：
这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。
本题则是装满有几种方法。其实这就是一个组合问题了。
code1：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) sum += nums[i];
if (abs(target) > sum) return 0; // 此时没有方案
if ((target + sum) % 2 == 1) return 0; // 此时没有方案
int bagSize = (target + sum) / 2;
vector<int> dp(bagSize + 1, 0);
dp[0] = 1;
for (int i = 0; i < nums.size(); i++) {
for (int j = bagSize; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
}
};
code2：
二维dp：以下写明五步曲的部分步骤：
1.确定dp数组以及下标的含义
现在算是体会到这个的重要性了
先用 二维 dp数组求解本题，dp[i][j]：使用 下标为[0, i]的nums[i]能够凑满j（包括j）这么大容量的包，有dp[i][j]种方法。
2.确定递推公式
二维廷简单的，跟之前讲的二维dp公式一致
-
不放物品i：即背包容量为j，里面不放物品i，装满有dp[i - 1][j]中方法。
-
放物品i： 即：先空出物品i的容量，背包容量为（j - 物品i容量），放满背包有 dp[i - 1][j - 物品i容量] 种方法。
本题中，物品i的容量是nums[i]，价值也是nums[i]。
递推公式：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
此时应该注意到，j - nums[i] 作为数组下标，如果 j - nums[i] 小于零呢？
说明背包容量装不下 物品i，所以此时装满背包的方法值 等于 不放物品i的装满背包的方法，即：dp[i][j] = dp[i - 1][j];
所以递推公式：
if (nums[i] > j) dp[i][j] = dp[i - 1][j];
else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];3.dp数组的初始化
只有背包容量为 物品0 的容量的时候，方法为1，正好装满。
其他情况下，要不是装不满，要不是装不下。
所以初始化：dp[0][nums[0]] = 1 ，其他均为0 。
左边一列就是 2^t种，初始化为：
int numZero = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 0) numZero++;
dp[i][0] = (int) pow(2.0, numZero);
}全部代码如下：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) sum += nums[i];
if (abs(target) > sum) return 0; // 此时没有方案
if ((target + sum) % 2 == 1) return 0; // 此时没有方案
int bagSize = (target + sum) / 2;
vector<vector<int>> dp(nums.size(), vector<int>(bagSize + 1, 0));
// 初始化最上行
if (nums[0] <= bagSize) dp[0][nums[0]] = 1;
// 初始化最左列，最左列其他数值在递推公式中就完成了赋值
dp[0][0] = 1;
int numZero = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 0) numZero++;
dp[i][0] = (int) pow(2.0, numZero);
}
// 以下遍历顺序行列可以颠倒
for (int i = 1; i < nums.size(); i++) { // 行，遍历物品
for (int j = 0; j <= bagSize; j++) { // 列，遍历背包
if (nums[i] > j) dp[i][j] = dp[i - 1][j];
else dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
}
}
return dp[nums.size() - 1][bagSize];
}
};474、一和零
力扣题目链接
题目描述：
给你一个二进制字符串数组 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 。
思路分析：
本题中strs 数组里的元素就是物品，每个物品都是一个！
而m 和 n相当于是一个背包，两个维度的背包。
1.确定dp数组（dp table）以及下标的含义
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
五步曲：
2.确定递推公式
dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
然后我们在遍历的过程中，取dp[i][j]的最大值。
所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
此时大家可以回想一下01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。
3.初始化
如上
4.遍历顺序
如上
5.举例推导dp数组√
code：
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
for (string str : strs) { // 遍历物品
int oneNum = 0, zeroNum = 0;
for (char c : str) {
if (c == '0') zeroNum++;
else oneNum++;
}
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];
}
};
