目录
四 拒绝被题意误导，看似背包问题，实际非背包问题，需要发现重复子问题
本文我们将会讲解动态规划中一个出现频次最高的问题——背包问题，背包问题是什么呢？简单来说，就是一些带有限制条件的组合的问题，背包问题最常见的问法就是：你有一个背包（背包有体积/重量或者其他条件的限制），可以选择给定的一些物品放进背包里（物品有属性，体积/重量/价值），背包能装的物品组合的最大价值？背包刚好装满时，物品的最大价值? 背包刚好装满有多少种装法？
对于背包而言，有两种情况： 刚好装满 和 不一定装满。
对于物品而言，有自己的属性，以及物品的数量限制。
根据物品的个数限制，背包问题又被分为三大类：
01 背包：所有的物品只有一个，只有选和不选两种情况
完全背包：所有的物品都有无限个，可以不选，选一个，选两个... ...
多重背包：每个物品的个数由题目给出，比如第i个物品由 cnt[i] 个
同时，根据背包的限制，也会进一步细分为几类问题，不过我们不需要关注背包的所有的分类，只需要掌握了 01 背包，那么其他类型的背包问题就只是01背包背包的变形，很好理解，所有背包问题最基础就是最重要的就是01背包。
一 01背包问题
1 01背包模板
解析题目：题目给定背包容量为 V ，物品种类为 n ， 每一类物品只有一个，然后给定物品的体积和价值，要我们求两个问题：1 背包能够装的最大价值 2 背包刚好装满时的最大价值。
在背包问题中，我们一般对物品的编号是从 1 开始，这相当于是做背包问题时的一个便于理解的小技巧，会在我们后续的状态表示中体现出来。
先不管其他，我们首先将所有的物品的体积和价值存储起来，由于我们背包问题对物品的编号从1开始，那么存储的下标我们也可以从1开始。
int n ;
cin>>n;
vector<int> v(n+1) , w(n+1); //由于我们默认编号从1开始，那么存储的时候也从下标1开始，便于状态表示
//v[i] 表示第 i 个物品的体积，w[i]表示第 i 个物品的价值
for(int i = 1 ; i <= n ; ++i){
cin>>v[i]>>w[i];
}
(1).背包能装的最大的物品价值
既然是动态规划问题，首先我们尝试一下定义一个一维的状态表示，看能否解决问题，因为每一个物品都有选和不选两种选择，那么我们其实可以根据物品的选择范围，也就是限制只能从哪些物品中进行选择，来进行子问题拆解以及状态表示，那么我们暂且定义状态表示为:
dp[i] 表示从前 i 个物品中进行选择，能够装进背包的最大价值。注意这里的前i个物品指的是下标在[1,i]范围内的物品。
那么我们尝试一下根据这个简单的状态表示能够推导出状态转移方程，对于dp[i]，我们根据最后一个物品的选和不选划分为两类情况：1、选择最后一个物品，那么装进背包的总价值需要加上w[i]，同时我们需要的是最大的价值，那么剩下的前 i-1 个物品我们也需要使用价值最大的选择方案，也就是dp[i-1]，那么此时dp[i] = dp[i-1] + w[i] (似乎是这样的？？真的这么简单吗？) 2、不选择第 i 个物品，此时选择在前 i 个物品选择的最大价值其实就是在前 i - 1 个物品中进行选择的最大价值，也就是 dp[i] = dp[i-1] 。
但是！！！我们是否忘了一个背包问题最重要的东西，就是背包的体积或者说背包的容量，我们所有的物品的不选或许不需要考虑容量问题，但是如果要选择某个物品，那么必须要满足把这个物品装进背包之后，物品的总体积不能超过背包的容量。但是我们的状态表示中，根本就没有体现任何关于背包的容量的信息，所以我们这个状态标识过于简单，无法解决01背包问题。
那么既然一维的dp表解决不了，我们可以尝试用一个二维的dp表，既然我们在推到状态转移方程的时候需要背包的容量来进行判断，那么我们可以在定义一个状态来表示当前背包的容量。在本问中，由于并没有规定背包必须要装满，只需要不超过体积限制就行了，那么我们就可以这样定义状态表示方程：
dp[i][j] 表示从前 i 个物品中选，总体积不超过 j ，此时所有选法的最大价值
状态转移方程推导：
我们还是根据最后一个物品的选和不选将dp[i][j]划分划分为两种情况：
1、选第i个物品，要满足选择第i个物品之后的总体积不超过j，就必须要保证在前i个物品中进行选择时，总体积不能超过 j - v[i] ，在前 i - 1 个物品中进行选择，总体积不能超过 j - v[i] ，那么前i-1个物品选择的最大价值就是 dp[i-1][j-v[i]] ，那么总的最大价值就是 dp[i][j] = dp[i-1][j-v[i]] + w[i]。但是这里我们需要考虑一种情况： j - v[i] < 0 ，也即是 j < v[i] ， 此时表示什么情况？ 意味着，光第i个物品的体积就超出了我们dp[i][j]的体积限制，那么此时还能选择第 i 个物品吗？当然不能。所以在选择第 i 个物品的时候，是有一个前提条件的，就是 j >= v[i] 。
2、不选第i个物品，那么此时问题就可以转换为：从前i-1个物品中进行选择，总体积不超过 j ，所有选法中的最大价值，也就是dp[i-1][j]，那么此时dp[i][j]=dp[i-1][j]。
那么综上，要使dp[i][j]的价值最大，我们需要取这两种情况的较大值
但是如果我们直接取max，那么由于第一种情况是有可能不存在的，我们怎么编写代码更方便呢？由于第二种情况是必然存在的，而第一种情况需要条件，那么不管怎么说，我们都可以先将dp[i][j]填为dp[i-1][j]，然后再去判断第一种情况是否存在，是否需要取较大值。
dp[i][j] = dp[i-1][j];
if(j >= v[i]) dp[i][j] = max(dp[i][j] , dp[i-1][j-v[i]]+w[i])
细节问题：
初始化：由于dp[i][j] 表示的是从前 i 个物品中选择，总体积不超过 j 的选法中的最大价值，我们的dp表其实跟前面的 v 和 w 表一样，是多开了空间的，也就是多开了一行和一列，那么如何进行初始化呢？首先dp[0][j]表示的是从前0个物品选择，体积不超过j的最大价值，因为没有物品可选，所有的方案都是一个空集，那么价值自然就是0，所以第一行我们初始化为0。那么第一列dp[i][0]如何初始化呢？第一列表示的是从前 i 个物品中选，总体积不超过0，最大的价值，那么毋庸置疑最大价值都是0，但是我们需要手动初始化第一列吗？
我们可以观察一下状态转移方程，对于第一列 dp[i][0]，由于所有的 v[i] > 0 ,也就是说不管是从前几个物品中进行选择，都只有一种情况，就是不选该物品，那么dp[i][0] = dp[i-1][0] ，最终所有的dp[i][0] = dp[0][0]，所以我们根本不需要初始化第一列，在填表过程中就能够根据状态转移方程将第一列初始化了。
综上，我们可以直接整个dp表初始化为0.
填表顺序：由于填写dp[i][j] 需要上一行的一个或者两个位置的值，所以填表一定是从上往下填写每一行，而每一行的填写顺序则没有要求。
返回值：我们需要的是背包能装的物品的最大价值，那么也就是从前i个物品中选择， 总体既不能超过V的最大价值，所以返回值就是 dp[n][V] 。
代码如下：
int n , V;
cin>>n>>V;
vector<int> v(n+1) , w(n+1); //由于我们默认编号从1开始，那么存储的时候也从下标1开始，便于状态表示
//v[i] 表示第 i 个物品的体积，w[i]表示第 i 个物品的价值
for(int i = 1 ; i <= n ; ++i){
cin>>v[i]>>w[i];
}
vector<vector<int>> dp(n+1,vector<int>(V+1)); //需要多开一行和一列
//1.背包能够装的物品的最大价值
//将第一行初始化为0
//填表
for(int i = 1 ; i <= n ; ++i){
for(int j = 0 ; j <= V ; ++j){ //由于第一列是在填表中初始化，所以j从0开始遍历
dp[i][j] = dp[i-1][j]; //不选第i个物品，最大的价值
if(j >= v[i]) //要选第i个物品必须要有前提条件
dp[i][j] = max(dp[i][j] , dp[i-1][j-v[i]] + w[i]);
}
}
//最后的结果就是在前i个物品中选，体积不超过V的最大价值 dp[n][V]
cout<<dp[n][V]<<endl;
(2).背包恰好装满时，物品的最大价值
第二问要求背包恰好装满，那么我们只需要稍微修改一下状态表示，定义状态标识为：
dp[i][j] 表示从前i个物品中选，总体积恰好为 j ，此时的最大价值
状态转移方程推导：
对于dp[i][j]，我们还是以最后一个物品的选和不选来划分情况
1、选择第i个物品，还是一样的，必须要满足 j >= v[i] 才有这种情况，那么选了第i个物品，前i-1个物品的体积就必须恰好是 j - v[i] ,所以 dp[i][j] = dp[i-1][j-v[i]] + w[i]。
2、不选择第i个物品，那么就是从前i-1个物品中选择总体积为j的方案，最大的价值，那么在这种情况下 dp[i][j] = dp[i-1][j]。
那么状态转移方程其实和第一问是一样的：
dp[i][j] = dp[i-1][j];
if(j >= v[i]) dp[i][j] = max(dp[i][j] , dp[i-1][j-v[i]]+w[i])
但是此时有一种特殊情况：从前i个物品进行选择，没有任何一种选法能够使得总体积为 j ，那么此时如何表示呢？此时表示dp[i][j]这种状态不存在。由于只要状态存在，也就是dp[i][j] 能够有一种方案达成，那么他的最大价值一定是大于等于0的，这表示的就是状态存在，那么我们只需要在dp表中用负数表示状态不存在就行了。如果dp[i][j] 为负数，表示无法从前i个物品中选择，恰好使总体积为j。
那么此时我们在状态转移方程中也要考虑状态不存在的时候如何填，比如第一种情况，如果状态不存在，也就是 dp[i-1][j-v[i]] < 0，那么就不能从dp[i-1][j-v[i]]转移到 dp[i][j]，对于第二种情况，如果dp[i-1][j] < 0 ，那么也不能由dp[i-1][j]转移到 dp[i][j]。如果两种情况都不存在，那么dp[i][j]中也需要填负数，表示dp[i][j] 状态不存在，但是只要有任何一种情况能够满足，那么dp[i][j] 就能从这种状态转移而来，填正数。
对于dp[i-1][j] 不存在这种情况还好说，因为只要dp[i-1][j]为负数，按照我们的状态转移方程，此时dp[i][j]会被填成负数，如果dp[i][j-v[i]]存在，那么就会被覆盖为正数。重点是 dp[i-1][j-v[i]]这个状态如何处理，因为我们再取这个状态的时候需要对其加上一个 w[i] ，那么原本dp[i-1][j-v[i]]是负数，加上w[i]之后就可能变成了正数，那么此时就和我们的逻辑冲突了。
其实也很简单，我么可以将不存在的状态初始化为负无穷大，那么后续不管其他的状态如何对其进行加 w[i]的操作，他也还是一个负数，表示不可由这种状态得到新的状态。
注意我们算法中的负无穷大一般用 -0x3f3f3f3f来表示，值大约为INT_MIN/2，他足够小，也能够保证对其进行减法的时候不会导致int的溢出。
细节问题：
初始化:需要初始化第一行，dp[0][j]，表示的是从前0个物品中进行选择，使得总体积恰好为j，此时的最大价值，由于没有物品可选，所有的方案都是一个空集，此时总体积只能是0，最大价值只能是0，那么我们需要初始化dp[0][0] = 0 ，而其他的值由于 j>0 ，那么这些状态是不存在的，所以其他的值都初始化为负无穷大。
对于第一列dp[i][0]，表示的是从前i个物品中进行选择，使得总体积为0，此时的最大价值，那么毋庸置疑他们都需要填 0 ，因为都只能选择一个空集，不选任何物品。但是由于我们的状态转移方程，所有的 dp[i][0] = dp[i-1][0] ，对于总体积为0的时候，只有不选第i个物品的情况，不会出现dp[i-1][j-v[i]]的情况，所以我们可以不需要手动初始化第一列，而在填表过程中由状态转移方程进行填写第一列。
填表顺序：由于填写dp[i][j]的时候会用到dp[i-1]这一行的一个或者两个位置的值，所以我们需要从上往下填写每一行，至于每一行中的填写顺序没有要求。
返回值：题目要求我们返回从n个物品进行选择，总体积恰好为V的最大价值，同时如果不存在这种方案，返回0，所以我们需要对dp[n][V]进行判断。如果dp[n][V]为负数，那么说明这种情况不存在，那么此时返回0，其他情况下返回 dp[n][V]就行。
代码如下：
//2.刚好装满背包的最大价值
//可以直接使用上面的dp表，规模是一样的
//初始化
for(int j = 1 ; j <= V ; ++j) dp[0][j] = -0x3f3f3f3f;
for(int i = 1 ; i <= n ; ++i){
for(int j = 0 ; j <= V ; ++j){
dp[i][j] = dp[i-1][j];
if(j >= v[i])
dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]] + w[i]);
}
}
cout<<(dp[n][V] >= 0 ? dp[n][V] : 0)<<endl;
空间优化
为什么在背包问题这里我们又要重新提空间优化了呢？因为背包问题最少都是一个二维dp表，会导致使用空间过大，如果数据量很大很大，那么会导致堆栈溢出，所以我们需要对背包问题的dp表进行优化，在背包问题中，我们都可以空间优化，优化掉一个维度。
首先我们观察状态转移方程，填写dp[i][j]的时候，只会用到dp[i-1]这一行的内容，也就是上一行的数据，那么其他的数据其实是没有必要继续占用空间来存储。那么我们最少最少可以将n+1行的dp表优化为2行，只需要2行就能够完成dp表的填写，不影响最终结果。
是否可以优化为一行呢？可以。
我们可以观察一下dp[i][j]，它只需要上一行对应位置的值和上一行的左边的值，同时每一次填写 dp[i][j]的时候都会首先将其赋值为dp[i-1][j]。
我们是不是可以直接用一个数组，同时存储dp[i-1] 和 dp[i]呢？因为当我们填写到dp[i][j]的时候，对于第i-1行，所有大于 j 的位置都没有用了，那么我们可以不用来覆盖填写第i行的值，而j前面的所有值还是旧值，也就是上一行的值，保证填表用的时候还是dp[i-1]这一行的值。
那么如果使用一个数组来填表的话，我们就需要 j 从大往小遍历了。
代码如下：
#include <iostream>
#include<vector>
using namespace std;
int main() {
int n , V;
cin>>n>>V;
vector<int> v(n+1) , w(n+1);
for(int i = 1 ; i <= n ; ++i){
cin>>v[i]>>w[i];
}
vector<int> dp(V+1);
for(int i = 1 ; i <= n ; ++i){
for(int j = V ; j >= 0 ; --j){
// dp[j] = dp[j]; //这一行代码不需要了
if(j >= v[i])
dp[j] = max(dp[j] , dp[j-v[i]] + w[i]);
}
}
cout<<dp[V]<<endl;
dp[0] = 0;
for(int j = 1 ; j <= V ; ++j) dp[j] = -0x3f3f3f3f;
for(int i = 1 ; i <= n ; ++i){
for(int j = V ; j >= 0 ; --j){
// dp[j] = dp[j];
if(j >= v[i])
dp[j] = max(dp[j],dp[j-v[i]] + w[i]);
}
}
cout<<(dp[V] >= 0 ? dp[V] : 0)<<endl;
return 0;
}
注意，空间优化并不改变我们的状态表示和状态转移方程，只是在原来的解题思路和方法的前提下对空间的进行优化。
那么除此之外，还有需要优化的地方吗？
首先，我们的dp表其实可以直接使用全局的dp数组，因为题目给定了数据范围为 1 <= n <= 1000，所以我们可以直接在使用一个1001的全局数组，同时我们使用的n和V等也可以使用全局的变量。
同时，我们观察这两部分代码：
两次填表过程中，只有在 j >= v[i] 的时候，dp[j]的值才会发生变化，否则都是直接继承上一行的dp[j]，那么为了减少j的遍历次数，我们是不是可以直接将这个 if 判断条件放到循环条件中呢？
#include <iostream>
#include<vector>
using namespace std;
int n , V ;
int w[1001],v[1001];
int dp[1001];
int main(){
cin>>n>>V;
for(int i = 1 ; i <= n ; ++i){
cin>>v[i]>>w[i];
}
for(int i = 1 ; i <= n ; ++i){
for(int j = V ; j >= v[i] ; --j){
dp[j] = max(dp[j] , dp[j-v[i]] + w[i]);
}
}
cout<<dp[V]<<endl;
dp[0] = 0;
for(int j = 1 ; j <= V ; ++j) dp[j] = -0x3f3f3f3f;
for(int i = 1 ; i <= n ; ++i){
for(int j = V ; j >= v[i] ; --j){
dp[j] = max(dp[j],dp[j-v[i]] + w[i]);
}
}
cout<<(dp[V] >= 0 ? dp[V] : 0)<<endl;
return 0;
}
几乎所有的背包问题都需要进行空间优化，否则很多时候都会提示空间溢出，我们优化的思路就是使用滚动数组，以及数组和变量尽可能在全局开辟，在静态区来存储
空间优化之后，我们不必强行去解释每一个位置的状态标识以及状态转移方程，因为我们的空间优化本身就是在一个完整且正确的动态规划的思路的前提下进行优化，仅仅是对空间的使用进行压缩，并没有对我们的基础框架进行修改。
接下来我们看几个典型的01背包的问题。
后续的01背包的问题我们都可以套用上面的01背包的状态表示以及状态转移方程的模板，空间优化的思路也是一样的，这一个模板题对于我们后面的背包问题具有重要的参考意义。
同时背包问题一般不会直接问，而是需要我们对原有题目意思进行一定的转换，然后才能发现是一个背包问题。
2 分割等和子集
解析题目：题目要求我们判断能否将整个nums数组分割为两个子集，使得两个子集的元素和相等。在第一次看到这个问题的时候，我们可能并不会将其和01背包结合起来，但是我们转换一下问题：对于两个子集，他们的和要想等，我们设nums数组元素的总和为 sum ，那么意味着两个子集的元素和都需要是 sum/2 ，我们只需要挑选出一部分元素，使其构成的子集的元素和为 sum/2,那么剩下的元素也作为一个子集，他们的总和也是sum/2，那么就能够分割成两个等和子集。
那么我们的问题就转换为了： 在数组中挑选任意个元素，使这些元素的总和为sum/2。
而对于nums中每一个元素，都只有选和不选两种情况，所以这就是一个典型的01背包问题，我们可以套用01背包的状态表示：
dp[i][j] 表示从前i个元素中选，能否使得元素的总和恰好为j
要注意的是，这里的前i个元素指的是下标[0,i-1]。
状态转移方程推到：
这是一个刚好装满背包的问题，所以我们有的状态是不存在的，不存在的话其实就是false，也就是没有方案能够满足条件。
对于dp[i][j]，我们还是根据最后一个元素的选和不选话分为两种情况：
1、选最后一个元素，此时有一个前提条件就是 j >= nums[i-1] ，因为如果j < nums[i] 的话，那么我们需要前i-1个数中挑选出总和为负数的情况，而nums所有元素都是正数，所以不会出现这种情况。那么此时dp[i][j] = dp[i-1][j-nums[i-1]]
2、不选最后一个元素，那么需要在前i-1个元素中看是否能够组成总和为j的子集，所以此时dp[i][j] = dp[i-1][j]。
而只要有一种情况能够使得dp[i][j]为true，那么结果就是true，所以状态转移方程如下：
dp[i][j] = dp[i-1][j];
if(j >= nums[i-1]) dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];
细节问题：
初始化：我们需要初始化多开的一行，dp[0][j]表示的是不选任何数，能否使得总和为j，只有当j=0的时候，才能够达成，其他情况下都是false。所以dp[0][0] = true;
对于第一列，所有的dp[i-1][0] = dp[i-1][0]，最终都会等于 dp[0][0]，这完全可以由状态转移方程来填表，所以我们不需要手动初始化第一列。
填表顺序：从上往下填写每一行，每一行的填表顺序没有要求。
返回值：dp[n][sum/2] ，n为nums元素个数，sum为nums元素总和。
同时我们可以在填表之前判断一下sum是否为偶数，如果不是偶数，那么一定无法分割出等和子集。
代码如下：
class Solution {
public:
bool dp[201][10001]; //n<=200,sum范围[1,20000],那么只需要开(n+1) *(sum/2+1)个就行了
int sum = 0 ;
bool canPartition(vector<int>& nums) {
for(auto e: nums) sum += e;
if(sum % 2) return false;
int n = nums.size();
dp[0][0] = true;
for(int i = 1 ;i <= n ; ++i){
for(int j = 0 ; j <= sum/2 ; ++j){
dp[i][j] = dp[i-1][j];
if(j >= nums[i-1]) //注意是 nums[i-1]
dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];
}
}
return dp[n][sum/2];
}
};
空间优化
我们可以优化掉一个维度，只需要使用一个一维数组就能完成填表。注意01背包优化空间之后，j的遍历必须要从大到小。
class Solution {
public:
bool dp[10001]; //n<=200,sum范围[1,20000],那么只需要开(n+1) *(sum/2+1)个就行了
int sum = 0 ;
bool canPartition(vector<int>& nums) {
for(auto e: nums) sum += e;
if(sum % 2) return false;
int n = nums.size();
dp[0] = true;
for(int i = 1 ;i <= n ; ++i){
for(int j = sum/2 ; j >= nums[i-1] ; --j){
dp[j] = dp[j] || dp[j-nums[i-1]];
}
}
return dp[sum/2];
}
};
3 目标和
本题有一种思路更加直接暴力，更容易想到的回溯的做法，代码如下：
class Solution {
public:
void TargetSum(int& count, int index,int sum,const vector<int>&nums,int target)
{
//优化
if(sum>target)
{
int endsum=sum;
for(int i=index;i<nums.size();++i)
{
endsum-=nums[i];
}
if(endsum>target)
return ;
}
if(sum<target)
{
int endsum=sum;
for(int i=index;i<nums.size();++i)
{
endsum+=nums[i];
}
if(endsum<target)
return ;
}
if(index==nums.size())
{
if(sum==target)
count++;
return;
}
TargetSum(count,index+1,sum+nums[index],nums,target);
TargetSum(count,index+1,sum-nums[index],nums,target);
}
int findTargetSumWays(vector<int>& nums, int target) {
/*//先排除出最坏情况
int allsum=0;
int allsub=0;
for(auto e:nums)
{
allsum+=e;
allsub-=e;
}
if(allsum<target || allsub>target)
return 0;
*/ //可以在递归的优化中直接检测出来
int count=0;
int index=0;
int sum=0;
TargetSum(count, index,sum,nums,target);
return count;
}
};题目解析：题目要求我们在nums的每个元素前面加上一个加号或者减号，构成一个表达式，要求最终表达式的结果为target，要我们返回有多少个这样的表达式。
nums所有元素都是正数，那么我们可以分析一下，在所有元素的前面加上加号和减号之后，那么所有加号的元素是一个集合，集合中的元素和是 sum1，所有减号的元素是一个集合，集合中的元素和是 sum2 ，那么最终表达式的结果就是 sum1 - sum2 ，我们需要让结果为 target，也就是：sum1 - sum2 = target，同时我们可以知道nums所有元素的总和sum，那么sum1+sum2 =sum，
那么根据这两个式子，我们可以将sum1或者sum2消元。最终得到:
sum1 = (target + sum)/2;
那么我们本题就转换为了：在nums中选择某些元素作为一个集合，使得集合的元素和为sum1，返回有多少种选法。 而每一个元素都只有两种情况，选和不选，那么这就是一个标准的01背包问题。参考01背包模板，我们定义状态表示为：
dp[i][j] 表示从前i个元素中选，使得总和为 sum1 的选法个数
那么这个题目和上一个题的区别就是本题要保存的是选法的个数，而上一个题只需要保存是否有对应的选法。
状态转移方程推导：
dp[i][j] 还是根据最后一个元素的情况话分为两种情况：
1、选第i个数，那么要求前i-1个数的和为 j-nums[i-1]，那么此时的方案其实就相当于在前i-1个数中进行选择，使得总和为 j - nums[i-1] 的这些方案的后面加上一个nums[i-1]，那么选第i个数的情况下，方案数dp[i][j]=dp[i-1][j-nums[i-1]].
2、不选第i个数，那么要求前i-1个数中选一些数使得他们的总和为 j ，那么这种情况下的方案数dp[i][j] = dp[i-1][j]。
那么对于dp[i][j]总的方案数就是这两种情况下的方案数的总和。
综上我们的状态转移方程如下：
dp[i][j] = dp[i-1][j];
if(j = nums[i-1]] dp[i][j] += dp[i-1][j-nums[i-1]];
细节问题：
初始化：我们会多开一行和一列的空间，对于第一行dp[0][j]表示的是不选任何数，使得总和为j的方案数，那么总和只能是0，只有空集一种方案，所以dp[0][0] = 1,其他的值都是0。而对于第一列dp[i][0]，由于nums中本身就有可能存在0，所以这一列的状态是需要状态转移方程推导出来的。
填表顺序：从上往下填写每一行，每一行的填写顺序没有要求。
返回值：dp[n][sum1]。 n为nums元素个数。
特殊情况：我们前面的推导都是基于sum1 > sum2 而言的，也就是target > 0，如果target = 0 或者target < 0，那么 sum 1 = (sum+target) / 2 其实有可能为0 或者甚至为负数，比如 target = -200,sum = 100，那么此时sum1就是一个负数，我们可以特殊处理，当sum1 < 0时，此时一定是没有任何方案能够使得总和为0的。当sum1= 0 时，由于nums中元素是可能为0的，那么我们也是需正常动态规划来求，只是由于sum1等于0，所以dp表列数为1，最终只有nums[i]是0的时候才会进行累加，累加的时候会累加 dp[i-1][0] 两次，这也正是我们想要的。
代码如下：
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size() , sum = 0;
for(auto e:nums) sum += e;
int sum1 = (sum + target) / 2;
if((sum + target) % 2) return 0;
if(sum1 < 0) return 0;
vector<vector<int>> dp(n+1,vector<int>(sum1+1));
dp[0][0] = 1;
for(int i = 1 ; i <= n ; ++i){
for(int j = 0 ; j <= sum1 ; ++j){
dp[i][j] = dp[i-1][j];
if(j >= nums[i-1]) dp[i][j] += dp[i-1][j-nums[i-1]];
}
}
return dp[n][sum1];
}
};
空间优化
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int n = nums.size() , sum = 0;
for(auto e:nums) sum += e;
int sum1 = (sum + target) / 2;
if((sum + target) % 2) return 0;
if(sum1 < 0) return 0;
vector<int> dp(sum1+1);
dp[0] = 1;
for(int i = 1 ; i <= n ; ++i){
for(int j = sum1 ; j >= nums[i-1] ; --j){
dp[j] += dp[j-nums[i-1]];
}
}
return dp[sum1];
}
};
4 最后一块石头的重量Ⅱ
解析题目：本题其实直接思考并不好相处思路，看似可以用贪心解决，但是其实怎么贪心并不好想，我们需要将其转换一下，然后使用动态规划来解决。
首先我们认为石头的重量为: {a,b,c,d,e,f,g};
我们假设最优的粉碎顺序如下:
1.a和b粉碎，那么剩余的石头重量为: { |a-b| , c,d,e,f,g};
2.c和e粉碎，那么剩余的石头重量为: {|a-b|,|c-e|,d,f,g};
3.两个粉碎过的石头进行粉碎，剩余的重量为:{| |a-b | - |c-e|| ,d,f,g}
3.d和f粉碎，剩余的重量为:{| |a-b | - |c-e|| ,|d-f|,g}
.... ....
那么我们发现到最后只剩下两块石头的时候，两块石头的重量其实就是原始的每块石头的重量的一个只含有加减符号的表达式，最终两块石头粉碎完之后，剩余的也是一个只含加减运算的表达式。
所以本题就转换为了:
在stones的每个元素前面添加加号或者减号，使得表达式的结果非负且最小，求这个最小的非负表达式结果。
那么这个题目就和上一个题一样了，我们再次进行转换，将添加加号的石头的重量总和记为 sum1,添加减号的石头的重量总和记为 sum2 ，那么我们需要使得 sum1 >= sum2且sum1-sum2最小，同时sum1+sum2 = sum。那么其实sum1和sum2都是越接近 总和sum 的一般越好。那么我们不妨以 sum2 作为边界条件来进行动态规划，因为sum2一定是小于等于sum/2的。
那么我们定义状态表示为:
dp[i][j] 表示从nums的前i个元素中选，使得所选集合的元素总和不超过 j时，最大元素总和。
状态转移方程推到：
对于dp[i][j]，我们还是以第i个元素的选和不选来划分为两种情况：
1、选择第i个元素，那么此时需要满足 j >= nums[i-1] 才能选第i个元素，在选第i个元素的情况下，我们要使元素总和不超过j的最大总和，那么就需要在前i-1个元素中选择，使得元素总和不超过 j-nums[i-1]，此时的最大总和，也就是 dp[i-1][j-nums[i-1]]，那么此时dp[i][j] = nums[i-1] + dp[i-1][j-nums[i-1]]；
2、不选第i个元素，那么此时只需要在前i-1个元素中选择总和不超过j时的最大总和，此时 dp[i][j]=dp[i-1][j]
综上所述，状态转移如下：
dp[i][j] = dp[i-1][j];
if(j >= nums[i-1]] dp[i][j] = max(dp[i][j],dp[i-1][j-nums[i-1]]+nums[i-1]);
细节问题：
初始化：我们需要手动初始化第一行，dp[0][j]，表示的是不选任何数，总和不超过j时的最大总和，那么毫无疑问都填0.对于第一列，我们不需要手动初始化，表示的是从前i个元素中选择总和不超过0的最大和，那么毫无疑问最终都是0，可以在状态转移时有dp[i-1][0]得到。
填表顺序：从上往下填写每一行，每一行的填写顺序没有要求。
返回值：sum - 2 * dp[n][sum2]; n表示 nums 的元素个数，sum1 - sum2 = (sum - sum2) - sum2
代码如下：
class Solution {
public:
int dp[31][3001]; //n<=30,sum<=3000
int lastStoneWeightII(vector<int>& stones) {
int n = stones.size() , sum = 0;
for(auto e: stones) sum += e;
for(int i = 1 ;i <= n ; ++i){
for(int j = 0 ; j <= sum/2 ; ++j){
dp[i][j] = dp[i-1][j];
if(j >= stones[i-1])
dp[i][j] = max(dp[i][j] , dp[i-1][j-stones[i-1]] + stones[i-1]);
}
}
return sum - 2*dp[n][sum/2];
}
};
空间优化
class Solution {
public:
int dp[3001]; //n<=30,sum<=3000
int lastStoneWeightII(vector<int>& stones) {
int n = stones.size() , sum = 0;
for(auto e: stones) sum += e;
for(int i = 1 ;i <= n ; ++i){
for(int j = sum/2 ; j >= stones[i-1] ; --j){
dp[j] = max(dp[j] , dp[j-stones[i-1]] + stones[i-1]);
}
}
return sum - 2*dp[sum/2];
}
};
二 完全背包
1 完全背包模板
题目解析：完全背包问题跟01背包问题的区别就是，每一种物品都有无限个，那么对于每一个物品的情况，就有无限种情况：不选，选一个，选两个，选三个。。。只要满足体积限制，我们就可以一直选。
完全背包和01背包只是在状态转移时有所区别，状态表示其实是一模一样的。
1.背包最多能装多大价值的东西
这个问题不要求背包装满，那么也就是总体积不超过背包总容量就行了，那么我们的状态表示就可以这样定义：
dp[i][j] 表示从前 i 种物品中选，总体积不超过j时的最大价值
状态转移方程推导：
其实也很简单，我们根据最后一种物品的选择情况来划分：
1、如果不选第i种物品，那么dp[i][j] = dp[i-1][j]
2、如果选第i种物品，那么此时又需要分为选一个该物品，选两个该物品，选三个。。。但是选择的物品数量一定要在体积限制条件下。
如果选一个 i 物品，那么前i-1类物品的总体积就不能超过 j - v[i] ,那么此时 dp[i][j] = w[i] + dp[i-1][j-v[i]]。
如果选两个 i 物品，那么前i-1类物品的总体积就不能超过 j - 2*v[i] ，那么此时dp[i][j] = 2*w[i] + dp[i-1][j-2*v[i]]。
以此类推，如果选 k 个i 物品，那么前i-1类物品的总体积就不能超过 j - k*v[i] ，此时dp[i][j] = k*w[i] + dp[i-1][j-k*v[i]]。
但是能否选 k 个i物品，需要满足条件 j >= k * v[i] ，也就是最多最多只能选择 j / v[i] 个i物品。
而我们需要最大的价值，就需要在这多种情况种取最大值，那么dp[i][j] 的状态转移方程如下：
但是这样一来，我们在填dp[i][j]的时候，就相当于需要多一层循环，当然如果时间限制没这么大，那么也是可以完成的，但是如果时间限制比较严格，那么就会导致超时。
我们需要将这一长串的状态转换为一个或者两个状态，这样一来填表时就更加方便了，或者我们可以说是化简状态转移方程，有两种方法： 1、 数学推导法 2、逻辑法（逻辑法我们在两个数组的dp问题中，通配符匹配和正则表达式匹配中用过，那里也可以用数学推导法得到）。
1 数学推导
我么可以发现状态转移方程中，取max 的项中，除了第一项，其他的项都依次多减了一个v[i]，那么我们可以推导一下 dp[i][j-v[i]]的状态转移方程：
这样一来，我们就能发现规律了，我们单独把dp[i][j]的第一项拿走，剩下的项来与dp[i][j-v[i]]比较：
我们能发现，上面的所有的项和下面的所有的项其实都只是差了一个 w[i] ,那么我们为dp[i][j-v[i]]加上一个w[i]，就变成了这样。
那么我们就能发现，dp[i][j] 的状态转移方程中，除了第一项，剩下的项可以等价为dp[i][j-v[i]]+w[i].
那么状态转移方程就可以简化为:
dp[i][j] = max(dp[i-1][j] , dp[i][j-v[i]]+w[i])
当然，这里的dp[i][j-v[i]]+w[i] 也只能在 j>= v[i]的情况下才存在，否则dp[i][j]就等于dp[i-1][j]。
逻辑推导：
我们还可以直接从逻辑上来解决：
由于dp[i][j]表示的是从前i中物品中进行选择，我们如果按照第i种物品的选和不选来划分情况的话，不选的话，dp[i][j] = dp[i-1][j] 。 如果选第i中物品的话，我们可以先选一个(在能够选一个的情况下)，剩下的体积就是 j - v[i] ，那么由于第i种物品可以继续选，那么剩下的 j - v[i] 的体积还是由前i种物品的选择方案构成，也就是在前i种物品中选择，使得体积不超过 j-v[i] 的最大价值，那么这就是dp[i][j-v[i]]。于是dp[i][j] = dp[i][j-v[i]] + w[i] (j>=v[i])。
为什么dp[i][j-v[i]]能够概括出所有的选择情况呢？也就是为什么能够表示选1个i物品，选2个i物品，选3个i物品....选k个i物品呢？
很简单，类似于递归函数，我们可以画一个展开图：
那么完全背包的填表就是这样的:
dp[i][j] = dp[i-1][j];
if(j >= v[i]) dp[i][j] = max(dp[i][j] , dp[i][j-v[i]]);
细节问题：
初始化：由于背包问题dp表天然多开一行和一列，我们需要手动初始化第一行，也就是dp[i][j]，表示的是没有任何物品可选，使得总体积不超过 j 的最大价值，那么毫无疑问都是0.
对于第一列，后续在填表的时候，会由填表语句全部初始化为0，所以我们不需要关心，同时由于我们在使用dp[i][j-v[i]]的时候是有一个if判断的前提，所以也不会越界。
填表顺序：从上往下填写每一行，每一行内的填写顺序没有要求。
返回值：dp[n][V] ，n表示物品的种类数，V表示背包最大体积
代码如下：
#include<iostream>
using namespace std;
int n , V;
int dp[1001][1001]; //全局dp表，n <= 1000,V<=1000,在main函数开始之前未初始化数据段会被全部初始化为0
int v[1001],w[1001]; //模板中，物品编号从1开始，存储体积和价值的下标也从1开始
int main() {
cin>>n>>V;
for(int i = 1 ; i <= n ; ++i)cin>>v[i]>>w[i];
//1.背包所能装的最大价值，体积不超过V
for(int i = 1 ; i <= n ; ++i){
for(int j = 0 ; j <= V ; ++j){
dp[i][j] = dp[i-1][j];
if(j >= v[i]) dp[i][j] = max(dp[i][j],dp[i][j-v[i]] + w[i]);
}
}
cout<<dp[n][V]<<endl;
//2.背包恰好装满时的最大价值
return 0;
}2.背包恰好装满时的最大价值
有了第一问的经验，第二问也就是手到擒来了，我们定义状态表示如下:
dp[i][j]表示从前i种物品中选，使得体积恰好为j，此时的最大价值
那么dp[i][j] 就有两种情况：不存在以及存在，不存在就表示没有任何一种方案能够使得在前i种物品中选体积为j，那么此时我们需要用一个负无穷来表示，为什么用负无穷呢？ 因为后续其他的位置如果用到了这个位置的值，也就是是用了dp[i][j] + w[x]，那么那么这个结果不影响取max，同时也不会影响他继续是无穷小，表示状态不存在。
那么对于状态存在的情况下，我们按照最后一种物品的选和不选分为两种情况：
1、不选第i种物品：dp[i][j] = dp[i-1][j]
2、选第i种物品，我们可以最多选 j/v[i]个，那么这些所有选法的最大值就是dp[i][j-v[i]] + w[i]（推导在第一问中），但是要选第 i 种物品是需要前提条件的，也就是至少要能选一个，也就是 j >= v[i]。
那么状态转移方程如下：
dp[i][j] = max(dp[i-1][j] , dp[i][j-v[i] + w[i])
我们填表时的代码如下：
dp[i][j] = dp[i-1][j];
if(j >= v[i]) dp[i][j] = max(dp[i][j],dp[i][j-v[i]]+w[i]);
细节问题：
初始化：背包问题的dp表天然多处一行和一列，我们需要手动初始化第一行dp[0][j]，表示的是没有任何物品可选的情况下，使得总体积恰好为j，此时的最大价值。那么由于没有物品可选，只有一个空集的情况，总体积为0，此时价值为0，也就是dp[0][0] = 0 。 而其他状态都不存在，也就是都填负无穷大。
而第一列的值可以在填表时由填表的正常代码使用 dp[i][0] = dp[i-1][0] 来填写，所以我们不需要手动初始化第一列。
填表顺序：从上往下填写每一行，每一行的填写顺序没有要求。
返回值：要返回总体积恰好为V的最大价值，有可能不存在方案使得总体积为V，所以我们需要判断dp[n][V]这个状态是否存在，如果小于0，表示不存在，那么此时按照题意需要返回0，如果存在就直接返回dp[n][V];
return dp[n][V] >= 0>dp[n][V] : 0;
代码如下：
//2.背包恰好装满时的最大价值
dp[0][0] = 0;
for(int j = 1 ; j <= V ; ++j) dp[0][j] = -0x3f3f3f3f; //初始化
for(int i = 1 ; i <= n ; ++i){
for(int j = 0 ; j <= V ; ++j){
dp[i][j] = dp[i-1][j];
if(j >= v[i]) dp[i][j] = max(dp[i][j] , dp[i][j-v[i]]+w[i]);
}
}
cout<<(dp[n][V] >= 0 ? dp[n][V] : 0) <<endl;
空间优化
完全背包问题与01背包问题一样，也可以优化为一维数组，使用滚动数组来模拟填表。
但是与01背包不同的是，由于 dp[i][j] = max(dp[i-1][j],dp[i][j-v[i]] + w[i]);dp[i][j]除了用到上一行同位置的值之外，还会用到同一行的左边的值，那么在填写dp[i][j]的时候，同一行左边的值必须已经更新完，所以在完全背包的滚动数组中，填表顺序是从左往右填。
同时由于当 j < v[i] 的时候，dp[i][j]只会继承dp[i-1][j]的值，那么在滚动数组中，我们就不需要管这些位置，所以我们可以将 if 判断优化到循环的条件中，j在遍历的时候直接从 v[i] 开始。
代码如下：
#include<iostream>
using namespace std;
int n , V;
int dp[1001];
int v[1001],w[1001];
int main() {
cin>>n>>V;
for(int i = 1 ; i <= n ; ++i)cin>>v[i]>>w[i];
//1.背包所能装的最大价值，体积不超过V
for(int i = 1 ; i <= n ; ++i){
for(int j = v[i] ; j <= V ; ++j)
dp[j] = max(dp[j],dp[j-v[i]] + w[i]);
}
cout<<dp[V]<<endl;
//2.背包恰好装满时的最大价值
dp[0] = 0;
for(int j = 1 ; j <= V ; ++j) dp[j] = -0x3f3f3f3f; //初始化
for(int i = 1 ; i <= n ; ++i){
for(int j = v[i] ; j <= V ; ++j)
dp[j] = max(dp[j] , dp[j-v[i]]+w[i]);
}
cout<<(dp[V] >= 0 ? dp[V] : 0) <<endl;
return 0;
}2 零钱兑换
解析题目：本题给定我们硬币的种类(面额)，我们可以理解为物品的体积和价值都是面额本身，然后背包的总容量为 amount，我们需要使用给定的面额刚好凑成总容量，返回最小的硬币数，也就是物品最少的方案。
我们直接定义状态表示如下：
dp[i][j]表示在前i种硬币中选，使得刚好凑成总价值 j 的时候，最少的硬币数。
注意，这里的前i种硬币表示的是下标 [0,i-1]
状态转移方程推导：
还是根据最后一种物品的选和不选来话分为两种情况：
1、不选第i种硬币，那么就是在前i-1种物品中凑成总价值恰好为j，那么就是dp[i-1][j]。
2、选第i种硬币，此时有一个前提条件就是当前要凑成的总价值j要大于当前硬币的面额，j>=coins[i-1]。 第i种硬币的面额为coins[i-1],那么剩余的 j - coins[i-1] 的价值还是要有前i种硬币凑成，但是由于用了一个coins[i-1]硬币，所以数量要加1，dp[i][j]=dp[i][j-coins[i-1]]+1。
同时我们需要的是凑成j 的最少的硬币数，所以需要取这两种情况的较小值：
dp[i][j] = min(dp[i-1][j] , dpi][j-coins[i-1]] + 1);
但是还有一种情况就是状态不存在，也就是无法通过指定的硬币范围凑出指定的总面额，对于状态转移方程而言就是 dp[i-1][j] 和 dp[i][j-coins[i-1]] 这两个状态都有可能不存在，但是也有可能某一种存在，由于dp[i][j] 是取min，所以我们可以将不存在的状态初始化为 正无穷大，这样一来不会影响存在的状态。同时由于我们对所有的状态都最多只会进行 + 1 的操作，那么正无穷大加1之后还是正无穷大，仍然表示状态不存在。
细节问题：
初始化：由于dp表天然多出一行和一列，我们需要手动初始化第1行dp[0][j]，表示的是不选任何硬币凑成总额为j的最少硬币个数，那么所选方案只有一个空集，总价值为 0 ,硬币数为0，那么dp[0][0]= 0 ，其他状态不存在，初始化为正无穷。
而第一列不需要我们手动初始化，可以有填表的逻辑进行填写。
填表顺序：从上往下填写每一行，每一行的填写顺序没有要求。
返回值：dp[n][amount],但是因为有可能这个状态不存在，如果不存在，那么里面的值为正无穷大，也就是 >= 0x3f3f3f3f ，我们需要判断一下它的值来决定返回-1还是dp[n][amount]
代码如下：
class Solution {
public:
int dp[13][10001];
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
//初始化第一行
for(int j = 1 ; j <= amount ; ++j) dp[0][j] = 0x3f3f3f3f;
for(int i = 1 ; i <= n ; ++i){
for(int j = 0 ; j <= amount; ++j){
dp[i][j] = dp[i-1][j];
if(j >= coins[i-1]) dp[i][j] = min(dp[i][j] , dp[i][j-coins[i-1]] + 1);
}
}
return dp[n][amount] >= 0x3f3f3f3f ? -1 : dp[n][amount];
}
};
空间优化
class Solution {
public:
int dp[10001];
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
//初始化第一行
for(int j = 1 ; j <= amount ; ++j) dp[j] = 0x3f3f3f3f;
for(int i = 1 ; i <= n ; ++i){
for(int j = coins[i-1] ; j <= amount; ++j)
dp[j] = min(dp[j] , dp[j-coins[i-1]] + 1);
}
return dp[amount] >= 0x3f3f3f3f ? -1 : dp[amount];
}
};
3 零钱兑换Ⅱ
题目解析：题目给定我们硬币的面额种类，要求我们使用给定的面额凑出 amount 的总额，返回总的选择方案数。
那么我们定义状态表示为:
dp[i][j] 表示在前 i 种硬币中选择，使得总额恰好为 j 的方案总数
状态转移方程推推导：
还是根据第i种面额硬币的选和不选来划分为两种情况：
1、不选第i种面额的硬币，那么此时就是从前i-1种硬币中凑成总额为 j 的方案总数，dp[i][j] = dp[i-1][j]
2、选择第i种面额的硬币，需要前提条件 j >= coins[i-1]，此时可以有多种选法，选一个两个三个等等，但是所有的方案数都已经算在了dp[i][j-coins[i-1]] 中，此时dp[i][j] = dp[i][j-coins[i-1]]。
而dp[i][j]的方案总数是这两种情况的总方案数，那么状态转移方程如下：
dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
需要注意的是，dp表中并不是所有的状态都存在，比如状态转移方程中 dp[i-1][j] 和 dp[i][j-coins[i-1]]这两个状态都有可能不存在，也就是使用指定范围的硬币可能凑不出对应的总额，那么此时需要怎么表示不存在的状态呢？对于不存在的状态，顾名思义，就是没有方案能够凑出指定的金额，那么方案数就是0，所以我们不需要额外定义正无穷或者负无穷为不存在。
细节问题：
初始化：由于背包问题的dp表天然都开一行和一列，所以我们需要手动初始化第一行dp[0][j]，表示的是不选任何硬币，凑成金额为j的方案数，此时只有一种情况就是空集，总金额为0，那么dp[0][0] = 1，而其他的位置则为0.
第一列由于可以在填表逻辑中进行初始化，所有的dp[i][0]最终都会等于 dp[0][0]，表示只有空集的情况下能使得总金额为0.
填表顺序：从上往下填写每一行，每一行内的填写顺序没有要求
返回值： dp[n][amount]，不需要判断状态是否存在。
还需要注意一点，虽然题目规定了最终的返回值在32为正数范围内，但是我们的中间位置可能会超出int 甚至long long的范围，所以我们可以使用unsigned long long 或者double来存储
代码如下：
class Solution {
public:
unsigned long long dp[301][5001];
int change(int amount, vector<int>& coins) {
int n = coins.size();
dp[0][0] = 1;
for(int i = 1 ; i <= n ; ++i){
for(int j = 0 ; j <= amount ; ++j){
dp[i][j] = dp[i-1][j];
if(j >= coins[i-1]) dp[i][j] += dp[i][j-coins[i-1]];
}
}
return dp[n][amount];
}
};
空间优化
class Solution {
public:
unsigned long long dp[5001];
int change(int amount, vector<int>& coins) {
int n = coins.size();
dp[0] = 1;
for(int i = 1 ; i <= n ; ++i){
for(int j = coins[i-1] ; j <= amount ; ++j){
dp[j] = dp[j];
if(j >= coins[i-1]) dp[j] += dp[j-coins[i-1]];
}
}
return dp[amount];
}
};
4 完全平方数
题目解析：题目给定一个数字，要求我们使用若干个完全平方数的和来构成这个数字，返回所需要的最少的完全平方数的数量。完全平方数其实就是 1^2 , 2^2 ,3^2 ,4^2 ....。
我们稍微将题目意思转换一下：给定多种硬币，硬币金额为 1,4,9,16,25 ... ... ，求出总金额恰好为n的最少硬币数，那么这个题其实就和零钱兑换完全一样了。
那么在构建 n 的时候会用到的最大的完全平方数是多少呢？ sqrt(n) ，这其实就相当于硬币的种类数。
那么我们可以定义状态表示如下：
dp[i][j] 表示使用前 i 个完全平方数构成总和为 j ，所需的最少的完全平方数的数量。
分析状态转移方程：
我们还是根据第 i 个完全平方数的情况划分情况
1、不选第i个完全平方数，那么此时就是在前i-1个完全平方数中取凑成总和为j，此时需要最少的完全平方数的数量就是 dp[i][j] = dp[i-1][j] ;
2、选第i个完全平方数，这种情况的前提就是 j >= i ^ 2 ，也就是j本身要大于等于第i个完全平方数，但是此时有多种情况，选1个，2个，3个... ... ,但是这些所有的情况可以用一个状态来总结就是 dp[i][j-i*i] ，那么此时dp[i][j] = dp[i][j-i*i] + 1;
而我们需要的是构建 j 的最少的完全平方数的数量，那么需要取这两种情况的较小值：
dp[i][j] = min(dp[i-1][j] , dp[i][j-i*i] + 1)
同时由于第一个完全平方数为1，所以只要n>0都能够由完全平方数恰好构成，只要 i>0&&j > 0 状态都存在。
细节问题：
初始化：背包问题的dp表天然多一行和一列，所以我们需要手动初始化第一行dp[0][j]，表示不选任何完全平方数，刚好凑成总和为j的完全平方数的最少数量，那么此时只有一种方案就是空集，总和为0，那么dp[0][0] = 0,其他状态都不存在，我们可以初始化为正无穷，因为后续的状态转移是取min，正无穷不会影响后续的结果。
而第一列可以在填表过程中由状态转移方程初始化，不需要我们手动初始化。
填表顺序：从上往下填写每一行，每一行内不要求填表顺序。
返回值：dp[sqrt(n)][n]
代码如下：
class Solution {
int dp[101][10001];
public:
int numSquares(int n) {
int len = sqrt(n);
for(int j = 1 ; j <= n ; ++j) dp[0][j] = 0x3f3f3f3f;
dp[0][0] = 0;
for(int i = 1 ; i <= len ; ++i){
for(int j = 0 ; j <= n ; ++j){
dp[i][j] = dp[i-1][j];
if(j >= i * i) dp[i][j] = min(dp[i][j],dp[i][j-i*i] + 1);
}
}
return dp[len][n];
}
};
空间优化
class Solution {
int dp[10001];
public:
int numSquares(int n) {
int len = sqrt(n);
for(int j = 1 ; j <= n ; ++j) dp[j] = 0x3f3f3f3f;
dp[0] = 0;
for(int i = 1 ; i <= len ; ++i){
for(int j = i * i ; j <= n ; ++j){
dp[j] = min(dp[j],dp[j-i*i] + 1);
}
}
return dp[n];
}
};
三 二维费用的背包问题
所谓的二维费用，指的就是每个物品不止体积和价值两个属性，还有一个其他的属性，背包的容量限制不止一种限制，而是两种， 比如背包的体积为V，最大重量为W，然后要求我们求不超过总容量或者恰好为总容量的最大价值。
1 一和零
解析题目：题目给定一个字符串数组，数组中每一个字符串都是由0和1这两种字符构成，要求我们从字符串数组中选择某些字符串，组成一个集合，集合中0的总数不超过m，1的总数不超过n，在所有满足条件的集合中，我们需要求出字符串数量最多的集合，返回其中字符串的个数。
那么我们可以将其解析为一个背包问题，由于每一个字符串只有选和不选两种情况，所以本题是一个二维费用的01背包问题。 背包的容量限制有两个：0的数量和1的数量。
字符串数组中的每个字符串可以看成是一个物品，物品的三个属性分别是0的数量，1的数量，字符串的数量(价值，就是1)。
我们可以参考01背包的状态定义，dp[i][j]只能表示从前i个字符串中选，0的数量不超过j，但是没有标识1的数量，那么我们可以定义一个三位的数组，如下：
dp[i][j][k] 表示在前i个字符串中选，使得0的数量不超过j，1的数量不超过k，组成的集合的字符串的最大数量。
状态转移方程推导：
根据第i个字符串的选和不选话分为两种情况：
1、不选第i个字符串(stars[i-1])，那么此时就是从前i-1个字符串中选，使得0的数量不超过j，1的数量不超过k的集合的最大字符串数量，那么dp[i][j][k] = dp[i-1][j][k]。
2、选择第i个字符串，而第i个字符串的0的数量我们记为 cnt0 , 1 的数量记为 cnt1 ，既然选了第i个字符串，那么剩余部分也就是前i-1个字符串的选法中，0的数量就不能超过 j - cnt0 ，1的数量就不能超过 k - cnt1 ，那么dp[i][j][k] = dp[i-1][j-cnt0][k-cnt1] + 1。在这种情况下，需要满足两个前提条件 : j >= cnt0 && k >= cnt1 ，如果不满足，则无法选第i个字符串。
那么状态转移方程如下：
dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-cnt0][k-cnt1] + 1)
填表逻辑：
dp[i][j][k] = dp[i-1][j][k];
if(j >= cnt0 && k >= cnt1) dp[i][j] = max(dp[i][j][k] , dp[i-1][j-cnt0][k-cnt1])
细节问题：
初始化：背包问题默认每个维度会多开一个空间，我们需要初始化 i = 0 的二维数组dp[0][j][k]，此时表示的是不选任何字符串，使得 0 的数量不超过 i ，1的数量不超过k，此时集合的字符串的最大数量，毫无疑问初始化为0。
而 j = 0 和 k = 0 依旧会在填表过程中被初始化，不选哟我们手动初始化。
填表顺序： i 从小到大，而j和k的顺序没有要求。
返回值: dp[len][m][n] ,len表示字符串数组的长度。
代码如下：
class Solution {
int dp[601][101][101];
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int len = strs.size();
for(int i = 1 ; i <= len ; ++i){
//预处理保存第i个字符串的01数量
int cnt0 = 0 , cnt1 = 0;
for(auto ch : strs[i-1]){
if(ch == '0') cnt0++;
else cnt1++;
}
for(int j = 0 ; j <= m ; ++j){
for(int k = 0 ; k <= n ; ++k){
dp[i][j][k] = dp[i-1][j][k];
if(j >= cnt0 && k >= cnt1)
dp[i][j][k] = max(dp[i][j][k] , dp[i-1][j-cnt0][k-cnt1] + 1);
}
}
}
return dp[len][m][n];
}
};
空间优化
对于二维费用背包问题我们依旧可以进行空间优化，可以优化掉一个维度。
我们可以发现，填写dp[i][j][k] 的时候，只会用到 dp[i-1] 的数据，而 row < i-1 的所有数据其实不会再使用，所以我们还是可以使用滚动数据来优化。
由于 dp[i][j][k] 填表可能会用到 dp[i-1][j-cnt0][k-cnt1] ，也就是填写{i,j}位置的时候，会用到左边以及上面的位置的旧值，那么我们填表的时候，为了保证填写 {i,j}位置的时候，左边和上面的值还是旧值，那么 j 和 k 的遍历顺序就必须从大到小。同时，先遍历j还是先遍历k没有要求。我们可以把if的判断放到循环条件中。
代码如下：
class Solution {
int dp[101][101];
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int len = strs.size();
for(int i = 1 ; i <= len ; ++i){
//预处理保存第i个字符串的01数量
int cnt0 = 0 , cnt1 = 0;
for(auto ch : strs[i-1]){
if(ch == '0') cnt0++;
else cnt1++;
}
for(int j = m ; j >= cnt0 ; --j){
for(int k = n ; k >= cnt1 ; --k){
dp[j][k] = max(dp[j][k] , dp[j-cnt0][k-cnt1] + 1);
}
}
}
return dp[m][n];
}
};
2 盈利计划
解析题目：公司里有 n 个员工，有 m 种工作，每一种工作需要的员工数以及利润保存在group数组和profit数组中。要求我们选择某些工作，使用不超过 n 个员工，实现不少于 minprofit 的利润，问我们一共有多少种选法。
题目理解起来有点绕，但是知道题意之后就很简单了，从示例可以看出每一种工作最多只能完成依次，所以本体是一个二维费用的01背包问题。
那么根据题目的问法，我们定义状态表示如下：
dp[i][j][k]表示从前i种工作中选，使用不超过j名员工，创造不少于k的利润的选法数量
状态转移方程推导：
对于dp[i][j][k]，我们还是根据第i种工作的选和不选划分为两种情况：
1、不选第i种工作，那么就需要从前j中工作中选出人数不超过j，总利润不少于k的计划总数，dp[i][j][k] = dp[i-1][j][k]
2、选第i种工作，而第i种工作需要 group[i-1] 个员工，如果j < group[i]，那么说明我们不能选第i种 工作， 第i种工作会创造 profit[i-1]的利润，如果 k - profit[i-1] < 0 , 说明第i种工作就能创造大于 k 的利润，这是允许的，因为我们的利润要求是不少于。所以要选第i种工作，必须要满足 j >= group[i-1]这个前提条件。剩余的人数和利润就需要从前i-1种工作中得到满足，这些方案中加上一个第i种工作就是新的工作方案，那么dp[i][j][k] = dp[i][j-group[i-1]][k-profit[i-1]] ;但是由于我们在使用这个状态的时候只对j进行限制，j - group[i-1] 不会越界，但是k - profit[i-1]是可能越界的，那么这时候怎么办？ 按照以往的初始化的经验，我们能够知道，当 k ==0 的时候，dp[i-1][j][0] 表示在前i-1种工作中进行选择，总人数不超过j时所有的选法，那么这所有的选法其实都是满足利润不少于0的，因为不可能出现负的利润，那么在这些所有的选法如果满足人数要求，那么在这些方案的基础上再选一个第i种工作，由于第i种工作本身产生的利润就大于k了，所以这些方案都是满足dp[i][j][k]的条件的，那么我们不妨当 k < profit[i-1] 的时候，直接使用 dp[i-1][j][0]时的方案数，那么这种情况下的状态就可以表示为：dp[i][j][k] = dp[i][j-group[i-1]][(k-profit[i-1] >0 ?k-profit[i-1]:0]。
综上，dp[i][j][k]的方案总数是两种情况下的方案数之和，那么状态转移方程如下：
dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-group[i-1]][(k-profit[i-1] >0 ? k-profit[i-1]:0)]
填表逻辑：
dp[i][j][k] = dp[i-1][j][k];
if(j >= group[i-1]) dp[i][j][k] += dp[i-1][j-group[i-1]][(k-profit[i-1] > 0 ?k-profit[i-1] : 0)];
细节问题：
初始化：我们需要手动初始化 i = 0 的位置，dp[0][j][k] 表示的是不选任何工作，使用不超过j的人数，创造不少于k的利润的方案数，那么注定利润只能为0，而人数也只能为0，那么只有当 k = 0 的时候，方案数为1，也就是不选任何工作，而k!=0时方案数为0。
不需要我们手动初始化 j = 0 和 k = 0 的位置，填表过程中会根据填表逻辑进行填写。
填表顺序：i从小往大填，j和k的顺序没有要求
返回值：dp[len][n][minprofit] , len表示工作的数量。
填表过程需要注意，dp[i][j][k]填完之后需要对 1e9+7取模，因为题目已经明确说明结果可能很大，需要取模。
代码如下：
class Solution {
public:
long long dp[101][101][101];
const int MOD = 1e9+7;
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
int len = group.size();
for(int j = 0 ; j <= n ; ++j) dp[0][j][0] = 1;
for(int i = 1 ; i <= len ; ++i){
for(int j = 0 ; j <= n ; ++j){
for(int k = 0 ; k <= minProfit ; ++k){
dp[i][j][k] = dp[i-1][j][k];
if(j >= group[i-1])
dp[i][j][k] += dp[i-1][j-group[i-1]][(k-profit[i-1] >= 0 ? k-profit[i-1] : 0)];
dp[i][j][k] %= MOD; //注意取模
}
}
}
return dp[len][n][minProfit];
}
};
空间优化
class Solution {
public:
long long dp[101][101];
const int MOD = 1e9+7;
int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
int len = group.size();
for(int j = 0 ; j <= n ; ++j) dp[j][0] = 1;
for(int i = 1 ; i <= len ; ++i){
for(int j = n ; j >= group[i-1] ; --j){
for(int k = minProfit ; k >= 0 ; --k){
dp[j][k] += dp[j-group[i-1]][(k-profit[i-1] >= 0 ? k-profit[i-1] : 0)];
dp[j][k] %= MOD; //注意取模
}
}
}
return dp[n][minProfit];
}
};
四 拒绝被题意误导，看似背包问题，实际非背包问题，需要发现重复子问题
1 组合总和Ⅳ
解析题目：题目给我们一个数组，数组中的元素互不相同，要求我们用数组中的元素构成一个排列，每一个元素都可以多次使用，使得排列中的元素总和为target。 注意，虽然题目说的是求组合数量，但是示例中说不同顺序的序列被视作不同的组合，所以本质上是需要我们求排列的个数。
我们初看这个题，数组中的元素相当于有无限个，同时我们需要选出一些元素组成总和为target，可能就会想到完全背包，然后被困在完全背包的思路中，但是在背包问题的介绍中我们就明确说明了，背包问题只能解决组合的问题，在背包问题中不关注任何所选元素的位置，所以无法解决这类关注元素顺序的排列问题，那么需要这么解决呢？
跳脱出背包问题的思维，我们只需要分析一下一个排列如何能够使得总和为target。
由于排列的长度不是固定的，因为可能多种长度的排列都能够使得总和为target，我们先考虑该排列的最后一个元素，题目要求的排列一定是需要选择nums的元素的，而nums的元素大于等于1，所以我们的排列一定至少有一个元素，不需要考虑空集。
对于满足条件的排列的最后一个元素，有多种情况，我们可以枚举 nums 的所有元素 nums[j] 作为排列的最后一个元素，那么该排列中，除了最后一个元素 nums[j] ，剩余元素的总和就应该是 target - nums[j] ，那么该排列的前面所有元素有多少种排列呢？这就转换为了从nums中选取元素组成排列，使得排列的总和恰好等于 target - nums[j]，在这些排列的后面加上一个nums[j]就求得了我们需要的排列 ，这就是根问题的子问题。
也就是我们需要求出排列总和为指定数据的排列个数。
那么我们可以定义状态表示为:
dp[i] 表示从nums中选取元素构成排列，排列的总和为 i ，这样的排列的总个数。
状态转移方程推导：
对于dp[i]，需要使得排列总和为 i ，那么我们枚举所有的排列的最后一个元素的情况，最后一个元素我们可以尝试使用nums中所有的元素，比如使用nums[j]，那么排列中除去最后一个元素之后，剩余的排列(有可能是空)的总和就应该是 i - nums[j]，那么这些排列有多少种呢？ dp[i-nums[j]]，在这些排列后面加上一个 nums[j] 就组成了总和为 i 的排列，那么以nums[i]为结尾的排列总和为i的排列个数就是 dp[i-nums[j]]。当然这是有前提的，就是nums[j] <= i。那么所有满足条件的nums[j]都能够作为排列的最后一个元素存在，那么dp[i]就是这些所有的排列的个数的总和。
dp[i] =
细节问题：
初始化：我们需要初始化 dp[0] ，总和为0，那么只能是空排列，只有一种，那么dp[0] = 1 ； 或者说我们可以认为dp[0]是为了保证后续填表的正确性。
填表顺序：从左往右填表
返回值：dp[target]。
注意：虽然题目保证最终结果在int范围内，但是中间过程可能会溢出，所以我们直接用uint_t或者double。
代码如下：
class Solution {
public:
unsigned long long dp[1001];
int combinationSum4(vector<int>& nums, int target) {
dp[0] = 1;
for(int i = 1 ; i <= target ; ++i){
for(auto e : nums){
if(e <= i) dp[i] += dp[i-e];
}
}
return dp[target];
}
};
2 不同的二叉搜索树
题目解析：题目要求用我们用键值为1~n的节点构建搜索二叉树，搜索二叉树就是对于每一个节点，左子树的所有节点都小于本节点，右子树的所有节点的值都大于本节点。
那么根节点就要大于左子树的所有节点，小于右子树的所有节点，我们是否可以枚举根节点的值？
我们需要求出1~n可以构建的搜索二叉树的数量，首先枚举根节点为 1~n , 假设根节点为 i ，那么比 i 小的节点的个数就是 i - 1 ，那么左子树的规模就是 i - 1 个节点，左子树自身需要是一棵二叉搜索树，而左子树的所有节点就是 1~i-1，那么左子树的种类总数就是用 1~i-1的节点可以构建的搜索二叉树的数量，这不就是一个子问题？同时，根节点 i 的右子树需要大于i的节点，一共有 n - i 个节点大于 i ，那么右子树的规模就是 n - i ，右子树也需要是一棵二叉搜索树，那么右子树一共有多少种呢？ 问题就变成了使用 i+1 ~ n 一共能构建的搜索二叉树的数量，那么我们是不是可以转换一下：由于右子树的节点都大于 i ，那么我们是否从逻辑上对其都减去一个 i ，使得这些节点依旧满足搜索二叉树的规则，那么问题就转换为了使用 1~ n-i 去构建二叉树的数量，这也是一个重复子问题。而使用i作为根节点的二叉树的数量，就是一个组合的问题了，左子树有 x 中，右子树有y种，那么以i为根节点的搜索二叉树就有x*y种。那么问题就变成了我们需要知道使用 x 个节点构建出来的搜索二叉树的数量就行了。
那么我们可以定义状态表示为：
dp[i]表示使用 i 个节点(1~i)构建的搜索二叉树的总数。
那么分析状态转移方程：
对于dp[i]，使用 i 个节点构建二叉搜索树，那么我们可以选择 1~i 的任意一个节点 j 作为二叉搜索树根节点，那么他的左子树的规模就是 j - 1，左子树的种类数就是 dp[j-1] ，右子树的规模就是i-j，右子树的种类数就有 dp[i-j]，总的种类数就是 dp[j-1] * dp[i-j]。那么dp[i]就是所有的dp[j-1]*dp[i-j]的和。
细节问题：
初始化：我们需要初始化 dp[0]，dp[0]其实就是一棵空树，只有一种，那么dp[0] = 1 ，也可以说是为了后续填表的准确性而将dp[0]初始化为1的
填表顺序：从左往右填表
返回值:dp[n]
代码如下：
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+1);
dp[0] = 1;
for(int i = 1 ; i <= n ; ++i){
for(int j = 1 ; j <= i ; ++j){ //枚举根节点
dp[i] += dp[j-1]*dp[i-j];
}
}
return dp[n];
}
}; 
总结
背包问题最基础也是最重要的就是01背包问题，只要掌握了01背包，其他背包问题其实只需要按照01背包的推导思路，基本都能解决。同时虽然学习了背包问题，但是我们要记住背包问题只是用于解决限定条件下的组合问题的，并不能解决需要顺序的排列问题，我们不能被困在了背包的思维中。