目录
DP41 【模板】01背包
leetcode 416.分割等和子集
leetcode 494.目标和
leetcode 1049.最后一块石头的重量Ⅱ
DP42 【模板】完全背包
leetcode 322.零钱兑换
leetcode 518.零钱兑换Ⅱ
leetcode 279.完全平方数
今天，我们将通过 8 道题目，来带各位了解并掌握动态规划中背包问题，但是只有01背包和完全背包，其中每种背包有四道题目，第一道是牛客上面的纯背包问题，算是模板，之后的都是leetcode上面的变形题目
（下文中的标题都是leedcode对应题目的链接）
DP41 【模板】01背包
首先我们需要知道，什么样的问题算是背包问题，就是，现在我有一个背包，然后我有很多物品，每一个物品都有自己的价值和体积，这时候就问你，要如何放置物品，才能使背包内的物品价值最高
然后又有两种情况，一种使需要恰好将背包装满，还有一种是可以不装满背包
而我们的 01 背包问题的核心就是，每一个物品都只有一个，你只有选或者不选
然后就是完全背包问题，这个就是每个物品都有无限多个，也是选或者不选
有了这样的理解之后，我们再来看一下上面的模板题，也就是给你一个数组，几个变量，一个是物品个数，一个是背包体积，仅此而已
先来解决第一问，然后再来解决刚好装满的情况
状态表示：在 i 位置之前的所有物品选择中，在 j 容量以内的能选择的最大价值
接着我们再来推导状态表示方程
当我们对 i 位置进行分析的时候，我们会发现一共有两种情况，一个是选，还有一个就是不选
先说说不选的情况，因为比较简单，如果我们不选的话，那么 dp[i][j] = dp[i-1][j]，代表没有当前位置时，前面所有情况中的最大值
如果我们选择当前位置的话，我们是不是得先看看容量够不够啊，而每一个物品有自己的体积，所以我们需要去 j - v[i] 位置去找（v 数组代表体积数组，当前总容量为 j）
所以 dp[i][j] = dp[i-1][j-v[i]]
但是此时又有一种情况了，就是：假设背包的总体积是10，但是这个物品自己的体积是100，那么显然是装不下的，所以我们在选择装这个物品之前，我们需要先判断一下，条件符合了我们才能进入后续的流程，也就是 j >= v[i]
而我们 dp[i][j] 的最终结果是两种情况的最大值
而不选的情况是一定存在的，选的情况不一定存在，所以我们可以先让 dp[i][j] 的值是不选的情况，然后再来判断，如果条件符合，再来走选的逻辑，还有比较最大的逻辑
最后是初始化和返回值，由于我们的状态表示方程中用到了 dp[i-1][j] 和 dp[i-1][j-v[i]]，所以我们需要在dp表的外面加上一圈以免防止越界，如下图：
加完之后也是要初始化的，首先是上面那一排，代表个数为 0 且容量在 i 以内时候的最大价值，既然个数为 0 了那么价值自然是 0
接着是左边那一列，代表容量为 0 时的最大价值，容量为 0，那么我们只能每一个物品都不选，所以总价值就都是 0
而我们的vector默认创建出来的时候就是 0，所以我们是不用初始化的
最后是返回值，由于我们的状态表示是：在 i 位置之前的所有物品选择中，在 j 容量以内的能选择的最大价值，所以我们的返回值就应该是最后一个元素，也就是dp[n][V]，n是物品个数，V是背包总体积，所以第一小问的代码如下：（这个代码是还没有空间优化过的，在最后会用滚动数组优化，各位可以耐心观看）
#include<bits/stdc++.h>
using namespace std;const int N = 1001;
int n, V, v[N], w[N];
int dp[N][N];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 = 1; j <= V; j++){dp[i][j] = dp[i-1][j];if(j >= v[i]) dp[i][j] = max(w[i]+dp[i-1][j-v[i]], dp[i][j]);}cout << dp[n][V] << endl;return 0;
}接着是第二小问，也就是刚好装满的情况
但其实大体逻辑都差不多，就是将一些细节问题改一改即可
首先还是两种情况，选或者不选，不选的话还是dp[i][j] = dp[i-1][j]
但是如果选的话，刚好装满的情况是不是又可能不存在啊，所以我们需要有一个约定，那就是，如果这个位置是没办法装满的，那么这个位置的值我们就设置为 -1
接下来我们的情况就大差不差了，都是 dp[i][j] = dp[i-1][j-v[i]]
只不过我们除了要判断一下 j >= v[i] 之外，我们还需要判断一下 dp[i-1][j - v[i]] 位置的值是否为 -1，如果为 -1 的话证明这种情况不存在，所以我们就不能进入选的逻辑
最后的小差别就在初始化上了，因为我们有了 -1 这个约定
首先是上面那一行，也就是物品个数为 0的请款，那么我们除了第一个位置为 0 之外，其他位置都需要是 -1，因为请款根本不存在
然后是左边那一列，也就是容量刚好是 0 的情况，我们每一个都不选就好了，所以就都是 0
总代码如下：（代码中的memset是因为dp表已经给用过了，所以要将里面的值全部置为0做一次清空）
#include<bits/stdc++.h>
using namespace std;const int N = 1001;
int n, V, v[N], w[N];
int dp[N][N];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 = 1; j <= V; j++){dp[i][j] = dp[i-1][j];if(j >= v[i]) dp[i][j] = max(w[i]+dp[i-1][j-v[i]], dp[i][j]);}cout << dp[n][V] << endl;memset(dp, 0, sizeof dp);for(int i = 1; i <= V; i++) dp[0][i] = -1;for(int i = 1; i <= n; i++)for(int j = 1; j <= V; j++){dp[i][j] = dp[i-1][j];if(j >= v[i] && dp[i-1][j - v[i]] != -1)dp[i][j] = max(dp[i][j], w[i] + dp[i-1][j - v[i]]);}cout << (dp[n][V] == -1 ? 0 : dp[n][V]) <<endl;return 0;
}最后就是空间优化了，这里我们将会采用滚动数组的形式做一个优化
我们先来想一想，当我们的dp表遍历到下面的时候，我们上面的部分是不是就不需要用到了啊，那么我们开辟那么大的空间不久浪费了吗，
所以第一种优化的方法就是，开两行数组，第一行先填表，填完之后，第二行按照第一行的数据进行填值，最后将第一行看作第二行，第二行看作第一行将以前的数据直接覆盖即可
但是这样子还是浪费空间了，因为我们可以只开一行
试想一下，我们要填 dp[i][j] 位置的时候，我们只会用到 dp[i-1][j] 和 dp[i-1][j-v[i]] 位置的值
也就是当前位置的正上方和正上方左边的值
那如果我们只开一行的话，我们只需要确保填表从右往左填不就好了，这样子我们就不会干扰到我们要的数据，同时也能将数据填进去
代码如下：
#include<bits/stdc++.h>
using namespace std;const int N = 1001;
int n, V, v[N], w[N];
int dp[N];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(w[i]+dp[j-v[i]], dp[j]);cout << dp[V] << endl;memset(dp, 0, sizeof dp);for(int i = 1; i <= V; i++) dp[i] = -1;for(int i = 1; i <= n; i++)for(int j = V; j >= v[i]; j--)if(dp[j - v[i]] != -1)dp[j] = max(dp[j], w[i] + dp[j - v[i]]);cout << (dp[V] == -1 ? 0 : dp[V]) <<endl;return 0;
}我们可以看到，我们的代码是直接降了一维的，而我们 j 的遍历顺序也变了，而 j 位置的判断条件变成了 j >= v[i]，这样子我们就可以直接省去 if 中的一个判断条件了
同时我们在 j >= v[i] 条件下，就不是每一次都遍历整表了，这样会有常数级别的时间提升
leetcode 416.分割等和子集
这道题目算是 01 背包问题的一个小变形
首先题目会给一个数组，问我们能不能将数组分成两个部分，使这两个部分的和相同
那么我们就需要将问题转换一下，首先我们知道所有元素的和为 sum，假设我们可以将这个数组分成两个和一样大的数组，两个数组内所有元素的和分别是 a、b，那么是不是就意味着 a+b = sum 且 a == b
那么我们就可以这么理解，一个背包容量为 sum / 2，接下来我们在一个数组中，通过选或不选某个物品，使其容量刚好等于 a（a == b，所以都可以）
这样我们一下就将问题转化成我们熟悉的问题了，接下来我就快进了，详细的在第一题的模板题中，讲得超级详细
首先，状态表示：在 i 位置以前的所有选法中，能否有和刚好为 j 的情况
那么我们就分为选或不选，不选的情况就是
dp[i][j] = dp[i-1][j];而我们选的情况就是
if(j >= nums[i-1]) dp[i][j] = dp[i-1][j-nums[i-1]];这里的判断是防止单个元素比容量还要大，至于判断刚好的逻辑，其实是不用判断的，因为只要选或者不选的情况有一个是 true，就证明这个情况是true，否则的话，就直接是false，如果前面都为false了，这个位置自然也是false
而且，我们会先让 dp[i][j] = dp[i-1][j]; 这样如果 dp[i][j] = dp[i-1][j]; 是false，且选的条件不符合，那么直接false就可以了
代码如下：
class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;for(auto e : nums) sum += e;if(sum % 2 == 1) return false;sum = sum / 2;int n = nums.size();vector<vector<bool>> dp(n+1, vector<bool>(sum+1));for(int i = 0; i <= n; i++) dp[i][0] = true;for(int i = 1; i <= n; i++){for(int j = 1; j <= sum; j++){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]] );}}return dp[n][sum];}
};然后是滚动数组优化空间：
具体逻辑在第一题都讲过了，这里就不再赘述了
class Solution {
public:bool canPartition(vector<int>& nums) {int sum = 0;for(auto e : nums) sum += e;if(sum % 2 == 1) return false;sum = sum / 2;int n = nums.size();vector<bool> dp(sum+1);dp[0] = true;for(int i = 1; i <= n; i++){for(int j = sum; j >= nums[i-1]; j--)dp[j] = (dp[j] || dp[j-nums[i-1]] );}return dp[sum];}
};leetcode 494.目标和
这一道题目其实没那么好看出是背包问题，题目就不解读了，直接开始分析
首先我们目标和是target，我们数组的所有元素加起来是sum，我们将数组里面的数分为 a 和 b，a 是所有正数的和，b 是所有负数的和的绝对值，那么我们就得到如下式子：
a + b = sum ①
a - b = target ②
所以，① + ② -> a = (sum + target) / 2
我们可以发现，在上述的式子中，我们是不需要求 b 的，只需要 a 就可以了
也就是，不需要找负数，只需要选或者不选当前正数，使他的和等于 (sum + target) / 2 即可，如果满足的话，证明当前选法存在，而我们现在要做的就是将所有选法都找出来
但是还有一种特殊情况就是，如果我的 (sum + target) 是一个奇数呢？除不尽啊，那么就意味着这道题目是没有结果的，直接返回 0 即可
状态表示：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[i][j] 的值就是两种情况相加
最后是初始化和返回值
为了防止越界，我们需要将dp表扩大一圈，最上面的一行代表数量为0，和为 j 的选法，除了第一个是 1 之外，其他的都是 0
最左边那一列代表和为 0 的选法，其实都是 1，但是最左边这一列我们是可以不用判断的
为什么这么说呢，我们来看看我们选的情况的条件判断，也就是当满足了 j >= nums[i-1] 这个条件的时候，我们才会进入选的逻辑，但是如果我们当前容量为 0，那么就是 0 >= nums[i-1]，除非是 0 == 0 的情况，否则是不可能进入的，因为是非负数组（题目条件）
所以我们其实可以让 j 从 0 位置开始遍历，填表的时候顺便将 0 位置的初始化工作一起做了
代码如下：
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0, n = nums.size();for(auto e : nums) sum += e;int a = (sum + target) / 2;if(a < 0 || (sum + target) % 2) return 0;vector<vector<int>> dp(n+1, vector<int>(a+1));dp[0][0] = 1;for(int i = 1; i <= n; i++){for(int j = 0; j <= a; 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][a];}
};空间优化后的代码如下：
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {int sum = 0, n = nums.size();for(auto e : nums) sum += e;int a = (sum + target) / 2;if(a < 0 || (sum + target) % 2) return 0;vector<int> dp(a+1);dp[0] = 1;for(int i = 1; i <= n; i++)for(int j = a; j >= nums[i-1]; j--)dp[j] += dp[j-nums[i-1]];return dp[a];}
};leetcode 1049.最后一块石头的重量Ⅱ
这道题目，其实是买了羊皮大衣的狼，写着中等，其实中间转换成背包问题的过程已经很接近困难题了
不解读，直接分析
我们会有一个数组，每个元素都是一个石头的重量，那么我们假设这个数组里面的元素是这样的：
{a、b、c、d、e}
先选 a、d 碰一碰，所以就是（假设a重）
{a - d、b、c、e}
接下来是 c、e碰一碰，假设e重
{a - d、b、e - c}
再然后是 a-d 和 b 碰一碰，假设 b 重
{b - a + d、e - c}
最后两个碰一碰，假设b-a+d重
{b - a + d - e + c}
所以我们可以看到，这个数组被分为了两个部分，一部分是正数，一部分是负数，而我们要求的其实是正数和负数的绝对值之间差最小的情况
其实如果你做过上一题，也就是目标和，那么相信你到这里已经知道怎么做了
既然要让这两个部分的差最小，那么我们就假设这两个部分相等好了
也就是 sum / 2，sum是整个数组所有元素的和
那么问题就转化成了，我们在这个数组中，选或者不选某个元素，使和最接近 sum / 2
又变成我们熟悉的 01 背包问题了，而且是没装满的情况
接下来就不详细讲解了，如果对背包问题本身有问题的话，请返回第一道模板题，那里真的讲得超级详细了......
代码如下：
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size(), sum = 0;for(auto e : stones) sum += e;int a = sum / 2;vector<vector<int>> dp(n+1, vector<int>(a+1));for(int i = 1; i <= n; i++){for(int j = 0; j <= a; 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][a];}
};空间优化后：
class Solution {
public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size(), sum = 0;for(auto e : stones) sum += e;int a = sum / 2;vector<int> dp(a+1);for(int i = 1; i <= n; i++)for(int j = a; j >= stones[i-1]; j--)dp[j] = max(dp[j], dp[j-stones[i-1]] + stones[i-1]);return sum - 2 * dp[a];}
};DP42 【模板】完全背包
在做题之前，我们先来谈一谈什么是完全背包，这和 01 背包问题有什么区别
01 背包的本质是，每个物品只有一件，而我们的完全背包问题是，每个物品有无数件，只要你的背包装得下，你就可以一直拿，仅此而已
所以我们的分析，和 01 背包还是有很多相同之处的
我们来看一下题目，给了一个背包体积，物品数量，价值，体积，分别两个问，一个是问的最大价值，还有一个是在刚好将背包装满的情况下的最大价值
先来看第一问：
状态表示：在 i 位置之前的所有选择中，在体积之和不超过 j 的前提下，所能选择的最大的价值是多少
接着我们来推导一下状态表示方程：
我们在 i 位置的时候有两种情况，选和不选
我们先来分析一下不选的情况：其实就是 dp[i][j] = dp[i-1][j]，这个和 01 背包一摸一样
接着就是选的情况，也是最不一样的地方
我们选的话，我们可以选一件当前物品，那么 dp[i][j] = dp[i-1][j - v[i]] + w[i]，其中v[i]代表当前物品的体积，w[i] 代表价值
如果我们选择两件的话，那么就是dp[i][j] = dp[i-1][j - 2 * v[i]] + 2 * w[i]
三件，四件...... 而我们要选择的是所有情况中的最大值，也就是：
dp[i][j] = max( dp[i-1][j]，dp[i-1][j - v[i]] + w[i]，dp[i-1][j - 2 * v[i]] + 2 * w[i] ...... )
面对这种情况，我们只能优化，将所有式子整合成一个或者两个式子
我们来看一下 dp[i][j - v[i]] 等于什么
dp[i][j - v[i]] = max( dp[i-1][j - v[i]] ，dp[i-1][j - 2 * v[i]] + w[i] ...... )
综上，我们可以得到，后面的式子全部可以用一个式子来表示，也就是：
dp[i][j] = max( dp[i][j - v[i]] + w[i] , dp[i-1][j] )
总结一下，这道完全背包问题分为两种情况，选或者不选，选的话就是
dp[i][j] = max( dp[i][j - v[i]] + w[i] , dp[i-1][j] )
不选的话就是 dp[i][j] = dp[i-1][j]
而我们要的是最大价值，所以我们应该选择这两种情况中的较大值
但是我们选的情况还有一个条件需要判断，也就是，如果我物品的体积为100，但是我的背包容量只有10，那么这种情况是不是就一定不能选择啊，所以我们还需要判断一下，也就是：
if(j >= v[i])
最后就是我们的初始化和返回值了
对于初始化，为了防止越界，所以我们需要在dp表外面加一圈
最上面那一行，也就是没有物品且容量为 j 的情况，那么没选物品那么价值自然就是 0
最左边那一行不考虑，因为我们选的时候有了判断条件，所以是不会越界的，只需要 j 位置从 0 开始往后遍历即可，这个在 01 背包问题中有详细讲解，目标和那道题目
返回值就是dp[n][V]，n是物品个数，V是背包容量
代码如下：
#include <bits/stdc++.h>
using namespace std;int main()
{const int N = 1001;int n, V, v[N], w[N];cin >> n >> V;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];int dp[N][N];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;return 0;
}同时我们还可以进行一下空间优化
当然，和 01 背包一样，我们都是用的滚动数组进行优化
同样的，还是用一行数组，但是这时候我们要填表的话，我们需要用到 dp[i-1][j] 和 dp[i][j-v[i]]
也就是正上方和左边的值，但是这个时候需要注意的是，因为只有一行，当我们没有进行下一次填表的时候，表上的数据都是 i-1 位置的数据，所以我们的填表是需要从左往右填表的
同时，我们在选择当前物品时，我们还有一个判断条件，也就是：j >= v[i]
而这时，我们可以让 j 直接从 v[i] 位置开始遍历，这样的话我们那个判断条件就可以直接舍去了
代码如下：
#include <bits/stdc++.h>
using namespace std;int main()
{const int N = 1001;int n, V, v[N], w[N];cin >> n >> V;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];int dp[N];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;return 0;
}接着是第二问，也就是刚好装满的情况，其实和第一问是差不多的，我们只需要修改几个细节即可
和 01 背包差不多，我们约定一下，如果这种情况不存在的话，我们就让这个地方的值为 -1
不选的情况是一样的，至于选的情况，我们就需要多判断一下了：除了要判断 j >= v[i]，还需要判断一下 dp[i][j - v[i]] 是否为 -1，如果两个有一个不满足，证明情况不存在，就不用选择
最后是初始化，因为返回值是一样的（特判一下 -1 的情况即可）
还是在外面多开一圈的空间，我们最左边的还是不用处理，选的时候有条件会筛选
最上面那一排代表的是，个数为 0，且容量为 j 的情况，那么就只有第一个值为 0，其他的情况都为 -1，因为都不可能存在
代码如下：
memset(dp, 0, sizeof dp);
for(int i = 1; i <= V; i++) dp[0][i] = -1;
for(int i = 1; i <= n; i++)
{for(int j = 0; j <= V; j++){dp[i][j] = dp[i-1][j];if(dp[i][j - v[i]] != -1 && j >= v[i])dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);}
}
cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;最后就是空间优化，这里就不过多赘述了，总代码如下：
#include <bits/stdc++.h>
using namespace std;int main()
{const int N = 1001;int n, V, v[N], w[N];cin >> n >> V;for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];int dp[N];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;memset(dp, -0x3f3f3f3f, sizeof dp);dp[0] = 0;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 ? 0 : dp[V]) << endl;return 0;
}leetcode 322.零钱兑换
这道题目，非常明显的背包问题，容量是整数amount，物品的个数和体积就是coins数组
再者，就是每个硬币数量都是无限的，就是在告诉你这道题目是完全背包
最后就是，他要刚好凑成总金额，所以就是刚好装满的情况
状态表示就是：在 i 位置以前的所有选法中，和刚好为 j 的最少需要选取的硬币的数量
选的情况就是：
if(j >= coins[i-1])dp[i][j] = dp[i][j-coins[i-1]] + 1不选的情况就是：
dp[i][j] = dp[i-1][j];而我们要的是最少的硬币数量，所以我们还需要对这两种情况做一个 min 的逻辑
代码如下：
代码中的0x3f3f3f3f 其实是INT_MAX 的一半，而我们之前用 -1 来表示不存在的情况，就是因为怕 -1 加上后面的价值出错了会影响判断逻辑，但是如果我们这个数组足够大的话，比如0x3f3f3f3f，那么即使我加上或者减去之后，都不会影响我们最后的结果
但是我们这里是不能用INT_MAX，以后有类似逻辑的地方也是不能使用INT_MIN的，因为这两个数代表着最大，如果我们涉及了加减法，那么会直接崩掉，0x3f3f3f3f 足够大，不会影响结果，他也足够小，可以进行加减法，所以是非常合适的
class Solution {
public:int coinChange(vector<int>& coins, int amount) {int n = coins.size();vector<vector<int>> dp(n+1, vector<int>(amount+1));for(int i = 1; i <= amount; i++) dp[0][i] = 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 coinChange(vector<int>& coins, int amount) {int n = coins.size();vector<int> dp(amount+1, 0x3f3f3f3f);dp[0] = 0;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]);}
};leetcode 518.零钱兑换Ⅱ
首先是状态表示：在 i 位置之前的所有组合中，所有容量等于 j 的组合数量的和
状态表示方程和上一道题目是一摸一样的，这里我就直接拿下来了：
选的情况就是：
if(j >= coins[i-1])dp[i][j] = dp[i][j-coins[i-1]] + 1不选的情况就是：
dp[i][j] = dp[i-1][j];而我们要的是所有组合的和，那么结果就应该是这两种情况相加，因为没有选 i 的时候有a种组合，选了之后有b种组合，这两类组合的和是相同的，那么他们内部就是不一样的，所以结果就应该是这两个的和
最后说一嘴，这里我们是不需要判断存不存在的，因为如果不存在的话，那么组合数就是 0，我们 0 加如何数都是 任何数本身，所以就不需要判断，让他等于 0 就好
同时这里还有一个非常炸裂的测试用例，所以我们需要用到unsigned int,虽然还是会越界，但是题目已经保证了至少结果不会越界
如果不想用unsigned int的话，你也可以直接...
这里我就直接放空间优化后的代码了，前面所有的题目都是有优化和没优化的版本的，如果要的何以去前面的代码中借鉴
代码如下：
class Solution {
public:int change(int amount, vector<int>& coins) {int n = coins.size(); vector<unsigned int> dp(amount+1);dp[0] = 1;for(int i = 0; i < n; i++)for(int j = coins[i]; j <= amount; j++)dp[j] += dp[j - coins[i]];return dp[amount];}
};leetcode 279.完全平方数
这道题目和之前的都大差不差
有两种做法，一种是直接整一个数组，将1~n的平方数放入数组中，那个数组就是我们背包问题中的物品，n就是背包的容量，接下来的还是选和不选的两种情况判断，最后是要刚好等于，也就是刚好装满的情况
而我们题目要求是返回最少数字相加的情况，所以我们这里还需要用上一个 min 的判断逻辑
同时，如果不想设置成-1（写代码的时候方便一点），我们还可以初始化成0x3f3f3f3f（这个在零钱兑换一那道题目的时候就有详细讲解了）
代码如下：
class Solution {
public:int numSquares(int n) {int m = sqrt(n);vector<int> dp(n+1, 0x3f3f3f3f);dp[0] = 0;for(int i = 1; i <= m; i++)for(int j = i*i; j <= n; j++)dp[j] = min(dp[j - i*i] + 1, dp[j]);return (dp[n] == 0x3f3f3f3f ? 0 : dp[n]);}
};今天这篇博客到这里就结束啦~(￣▽￣)~*
如果觉得对你有帮助的话，希望可以关注一下喔
