兜兜转转了半天，发现还是Carl写的好。
看过动态规划-基础的读者，大概都清楚。
动态规划是将大问题，分解成子问题。并将子问题的解储存下来，避免重复计算。
而背包问题，就是动态规划延申出来的一个大类。
而01背包，就隶属于背包问题。
那什么又是01背包呢？
01背包
有n件物品，与一次最多能背w重量的背包。第i件物品，重量为weight[i]，得到的价值为value[i]。
每件物品只能用一次，求解，将那些物品装入背包内，物品的价值总和最大。
| 重量(weight) | 价值(value) | |
|---|---|---|
| 物品0 | 1 | 15 |
| 物品1 | 3 | 20 |
| 物品2 | 4 | 30 |
这是一个标准的背包问题，很多一看到这个，就直接想起用动态规划，而忽略了暴力解法。
这是因为没有 自下而上 思考的结果。
如下代码，一般动态规划问题，都是能通过回溯解决，因为每个物品都有两种可能(状态)，
被放入背包，或者不放入背包。
// 全局变量用于记录最大价值
int maxValue = 0;
// 物品的重量和价值数组
vector<int> weights = {1, 3, 4, 5, 6};
vector<int> values = {1, 3, 4, 5, 6};
// 背包容量
int capacity = 10;
// 回溯函数
void backtrack(int index, int currentWeight, int currentValue) {
// 如果已经遍历完所有物品
if (index == weights.size()) {
// 更新最大价值
if (currentValue > maxValue) {
maxValue = currentValue;
}
return;
}
// 不选择当前物品 - 01背包中的0
backtrack(index + 1, currentWeight, currentValue);
// 选择当前物品 - 01背包中的1
if (currentWeight + weights[index] <= capacity) {
backtrack(index + 1, currentWeight + weights[index], currentValue + values[index]);
}
}
如上的回溯算法，每个问题都有两个解法，通过暴力解决，但通常这种解法，是O(2^n)的时间复杂度，随着数量的增加。
呈指数级上升。
而动态规划仅仅需要O(N*M)就可以解决。
第一步：下标含义
dp[i][j]表示将前i件物品装进限重为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=W第二步：推导公式
那么我们可以将dp[0][0...W]初始化为0，表示将前0个物品(即没有物品)，装入书包的最大价值为0。那么当i>0时，dp[i][j]有两种情况：
- 不装入第i件物品，即
dp[i−1][j]； - 装入第i件物品（前提是能装下），即dp[i-1][j-weight[i]]+value[i]。
第三步：书写代码
dp[weight.size()][bagweight + 1];
// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}压缩
递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
看到 dp[i][j] 与 dp[i-1][...] 的
大家都可以发现，dp都由上一行推导出来的(也就是把dp[i - 1]那一层拷贝到dp[i]上)，所以可以压缩代码。
把二维数组，压缩为一维滚动数组。
这也就是滚动数组的由来，需要满足的条件是上一层可以重复利用，直接拷贝到当前层。
需要注意的是，为了防止上一层循环的dp[0,...,j-1]被覆盖，循环的时候 j 只能逆向枚举
如下：
for(int i = 0; i < weight.size(); ++i){
for(int j = bagWeight; j>=weight[i]; j--){
dp[j] = max( dp[j], dp[j-weight[i]]+value[i] );
}
}大纲
1、分割等和子集
3、目标和
4、一和零
题目
1、分割等和子集
给你一个 只包含正整数 的 非空 数组
nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。提示：
1 <= nums.length <= 2001 <= nums[i] <= 100
class Solution {
// 最大也就意味着最接近
// 能通过动态规划解决的，都能通过回溯解决
// 每个数字都有两种状态，被选中，或者不被选中
// 只有单纯的数字，那么数字的大小是重量，也是价值。
public:
bool canPartition(vector<int>& nums) {
int cur = 0;
for(int i:nums) cur+=i;
int sum = cur/2;
if(sum*2 != cur) return false; // 意外情况，直接排除
vector<int> dp(sum+1,0);
for(int i=0; i<nums.size(); i++){
for(int j=sum; j>=nums[i]; --j){
dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]);
}
}
return sum==dp[sum]?true:false;
}
};2、最后一块石头的重量 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 <= 301 <= stones[i] <= 100
为啥要分两堆->一直在动态的动态的维护，从第一块进入开始，一直在动态的维护两堆的平衡。
class Solution {
// 对呐，只要让两拨石头血拼就行！
// 但是，为啥要让两拨石头血拼？
// 图片上附上解析，希望以后能看懂
public:
int lastStoneWeightII(vector<int>& stones) {
int sum = 0;
for(int i : stones) sum+=i;
int cur = sum;
sum>>=1; // 右移2位，相当于除以2；
vector<int> dp(sum+1, 0);
for(int i=0; i<stones.size(); ++i){
for(int j = sum; j>=stones[i]; --j){
dp[j] = max(dp[j],dp[j-stones[i]]+stones[i]);
}
}
return cur-2*dp[sum];
}
};3、目标和
给你一个非负整数数组
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 <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
class Solution {
// 如果用暴力解法，本题也是能做的
// 但是如果我不暴力呢？
// 了解过答案之后，就发现这道题目，纯纯是一道推理题。
// 用方法就行推理，真tm是一道推理题
// (cur+)+(cur-) = target;
// (cur+)-(cur-) = target;
// cur = (sum-target)/2; 由此公式推导
// 只要找到cur就OK了
// 当sum为0时，代表总和与target相同，都只有一种情况
public:
int findTargetSumWays(vector<int>& nums, int target) {
int cur = 0;
for(int i:nums) cur+=i;
int sum = (cur-target)>>1;
if(sum*2!=cur-target||sum<0) return 0; // 直接就没有可能了
vector<int> dp(sum+1);
dp[0]=1;
// 公式推导出来的正整数
for(int i=0; i<nums.size(); ++i){
for(int j=sum; j>=nums[i]; --j){
dp[j]=dp[j-nums[i]]+dp[j];
}
}
return dp[sum];
}
};
// ???我的脑袋里，有个大大的问题？这能过？？4、一和零
给你一个二进制字符串数组
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 。示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1 输出：2 解释：最大的子集是 {"0", "1"} ，所以答案是 2 。提示：
1 <= strs.length <= 6001 <= strs[i].length <= 100strs[i]仅由'0'和'1'组成1 <= m, n <= 100
class Solution {
// 直接就干到n的三次方了！我的天呐，太牛了
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(string str : strs){
int num0=0,num1=0;
for(char c : str){
if(c=='0') num0++;
else num1++;
}
for(int i=m; i>=num0; --i){
for(int j=n; j>=num1; --j){
dp[i][j] = max(dp[i][j],dp[i-num0][j-num1]+1);
}
}
}
return dp[m][n];
}
};完结（￣︶￣）↗ ，自己是收益匪浅啦
博客借鉴：