问题定义
首先先定义下背包问题，方便后面讲述： 有N件物品，W容量的背包，第 i 件物品的重量为 weight[i]，价值为 value[i]，问在能装下的前提下如何使得背包的物品价值最大。
具体的例子如下，背包的容量为4。显然最大的价值是35。
核心代码
首先回顾下两个核心代码：
0/1背包的核心代码：
for (int i = 0; i < weight.size(); i++) {
for (int j = bagWeight; j >= weight[i]; j--) {
dp[j] = max(dp[j], d[j-weight[i]] + value[i]);
}
}
完全背包的核心代码：
for (int i = 0; i < weight.size(); i++) {
for (int j = weight[i]; j <= bagWeght; j++) {
dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
}
}
可以看到这两个问题的差别只有内层for循环的顺序不同：
for (int j = bagWeight; j >= weight[i]; j--) // 0/1背包，使用的是逆序遍历
dp[j] = max(dp[j], d[j-weight[i]] + value[i]);
for (int j = weight[i]; j <= bagWeight; j++) // 完全背包，使用的是正序遍历
dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
为什么调整遍历的方向就可以？
按照最经典的例子，来看下每次更新的dp是怎样的，dp的大小应该是容量的大小+1，也就是5。这里要注意，很多时候我们是会多申请一个空间，dp[0]作为起始条件来推导使用。
对于0/1背包而言，当 i=0 遍历第一个物品时:
第一次遍历的过程：j=bagWeight=4，此时的条件是weight[i] = weight[0] = 1，dp[4]=max(dp[4], dp[4-1]+value[1]) = 15，结果如下：
第二次遍历的过程：j = 3，weight[i] = weight[0] = 1，dp[3] = max(dp[3], dp[3-1]+value[1]) = 15，结果如下:
遍历完第一个物品得到的结果为：
对于完全背包而言，当 i=0 遍历第一个物品时: 第一次遍历的过程：j=weight[i] = weight[0] = 1，条件是 bagWeight=4，dp[1] = max(dp[1], dp[1-1]+value[0]) = 15，结果如下：
第二次遍历的过程：j = 2，weight[i] = weight[0] = 1， dp[2] = max(dp[2], dp[2-1]+value[0]) = max(dp[2], dp[1]+value[0]) = 30，结果如下：
遍历完第一个物品得到的结果为：
回顾下在0/1背包问题和完全背包问题中dp的定义：
dp[j] 表示的是容量为 j 的背包所背物品的最大价值 -> 这个定义在两个问题中都是一致的。
通过上面的一个物品的遍历过程，可以看出两个遍历顺序带来的不同，在两个问题中是都需要利用之前的 dp 结果，也就是说dp[j] 需要用到dp[0...j-1]的结果，但是在完全背包问题中这些结果是已经计算过的，也就是说dp[0...j-1]已经放入了0个或多个物品了。而在0/1问题中，这些结果还没有计算，也就是没有放入物品的时候，每当计算到dp[i]的时候就只会放入一个物品。
应用举例
总结起来有三类问题，这里的核心代码根据题目会有一定的变通。遍历顺序只需要判断题目中"物品"能不能取多个来判断，多个就正向遍历，一个就逆向遍历。
解决问题的核心要点就是明确dp的定义，确定好初始化条件，然后明确遍历顺序，最后搞定！
其中遍历顺序上求的是组合数，就是外循环物品，内循环目标；如果是排列数，那就是外循环目标，内循环物品。
dp[j] = dp[j] || dp[j-nums[i]];
dp[j] += dp[j - nums[i]];
dp[i] = min(dp[i], dp[i - j*j]+1);
dp[i] = max(dp[i], dp[i - j*j]+1);
0/1背包
题目说明：将一个数组分割成两个和相同的子集，返回当前这个数组是否可以满足这个要求。
例子：[1, 5, 11, 5] 返回 true，因为可以分成 [1, 5, 5]和[11]
题目转化为0/1背包问题，就是在所有的数值中选，把数值当成物品，对应的数值大小就是value的大小，每个只能选一次，最终看能否选出和为所有数值总和一半的子集。 实现过程：
// 这种实现方法有点不好理解
bool canPartition(vector<int>& nums) {
int sum = 0;
vector<int> dp(10001, 0); // dp[i]表示用元素构成背包容量为i的总和
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
// 如果和为奇数，那么显然不能分成两个和相等的子集，题目要求为正整数
if (sum % 2 == 1) return false;
int target = sum / 2;
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]);
}
}
return dp[target] == target;
}
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
if (sum % 2 == 1) return false;
int target = sum / 2;
vector<bool> dp(target+1, false); // dp[i]表示的是i数值能否被nums中的数值构成
dp[0] = true; // 作为初始条件很重要，它的含义这里可以理解成数值0可以由任意的nums数组构成
for (int i = 0; i < nums.size(); i++) {
for (int j = target; j >= nums[i]; j--) {
dp[j] = dp[j] || dp[j-nums[i]];
}
}
return dp[target];
}
题目说明：给定一个数组，可以在数值前面添上+号或者-号，构成target的方式多少种？
例子：[1, 1, 1]，target = 1，那么就有三种构成方法，分别是 [-1, 1, 1] [1, -1, 1] [1, 1, -1]
这道题第一眼看起来可能会想到回溯方法来做，转化成背包问题需要一点技巧。
首先我们将数值的和分成两部分，这个时候是没有加符号的，两个部分和的大小由加入的数值决定。只是将两个数值和分成两部分。
现在给pos部分加上+号，neg部分加上-号，那么我们可以构建出以下等式：
pos−negpos+neg=target=sum 消掉 pos后得到：
neg=2sum−target 其中，sum和target都是已知的，那么neg也就是已知的，当然如果要转换成求pos也是可以的。
转化成背包问题就是从nums中选择数字，放进大小为neg的背包中。
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
int diff = sum - target;
if (diff < 0 || diff % 2 == 1) return 0;
int neg = diff / 2;
vector<int> dp(neg + 1, 0); // dp[j]表示的是j数值可以被nums构成的种类
dp[0] = 1; // 初始化条件，可以构成0大小的记为1次
for (int i = 0; i < nums.size(); i++) {
for (int j = neg; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[neg];
}
题目说明：给定一个0和1字符串的数组，找出满足m个0，n个1的最大子集长度。
举例说明：strs = ["10", "0", "1"]， m = 1，n = 1。那么结果为1，因为满足的子集为["10"] 和 ["0"]，["1"]，所以最大长度为2。
这道题就比较不一样了，不完全是相同的0/1背包的套路了。这道题是两个维度的0/1背包了。
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); // dp[i][j]表示的i个0和j个1构成的最大子集长度
for (const auto& str : strs) { // str相当于物品
int numZeros = 0, numOnes = 0;
for (const auto& c : str) {
if (c == '0') numZeros++;
else numOnes++;
}
for (int i = m; i >= numZeros; i--) { // 1维 0/1背包 容量为m
for (int j = n; j >= numOnes; j--) { // 2维 0/1背包 容量为n
dp[i][j] = max(dp[i][j], dp[i-numZeros][j-numOnes] + 1);
}
}
}
return dp[m][n];
}
完全背包
题目说明：给定金额大小，和一定数量的零钱，问构成零钱金额共有多少种方式，每种零钱可以取多个。
举例说明：amount = 5, coins = [1, 2, 5]，那么共有四种方案构成总金额，5 = 5； 5 = 2 + 2 + 1；5 = 2 + 1 + 1 + 1；5 = 1 + 1 + 1 + 1 + 1；
int change(int amount, vector<int>& coins) {
vector<int> dp(amount+1, 0);
dp[0] = 1;
for (int i = 0; i < coins.size(); i++) {
// 目标和题目中是这么写的了，注意对比两者的区别
// for (int j = amount; j >= coins[i]; j--)
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j-coins[i]];
}
}
return dp[amount];
}
题目说明：和零钱兑换是一样的，只不过这里的构成方案有顺序要求。
举例说明：target = 4, nums = [1, 2, 3]，构成target的共有7中方案：4 = 1 + 1 + 1 + 1; 4 = 1 + 1 + 2; 4 = 1 + 2 + 1; 4 = 2 + 1 + 1; 4 = 2 + 2; 4 = 1 + 2; 4 = 3 + 1;
可以看得出，这个时候组合的方式有了顺序的要求，也就是说[1, 2, 1] 和 [2, 1, 1]是不同的组合方式，而在零钱兑换这两种方式是一样的。
// 这个解法中有两个点需要注意
// 1. 官方题解中dp是用int来表示的，但是由于中间结果会溢出，所以在内层循环判断的时候加了dp[j] < INT_MAX - dp[j-nums[i]]的判断，但是要知道加了这个判断，算出来的dp结果是错误的！这一点很重要，只不过刚好这个结果又是对的，所以看起来这个判断是没有影响的。但是其实是有的，大家可以把对应溢出测试用例的dp数组打印出来对比下就知道了。去掉这个判断就是将int改成unsigned int就可以了。
// 2. 需要对比零钱兑换II的遍历方式，体会两者的差异
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned int> dp(target + 1, 0); // 如果是int类型中间结果会溢出
dp[0] = 1;
/* 零钱兑换II的遍历方式
for (int i = 0; i <= nums.size(); i++)
for (int j = nums[i]; j <= target; j++)
*/
for (int j = 1; j <= target; j++) {
for (int i = 0; i < nums.size(); i++) {
//if (j >= nums[i] && dp[j] < INT_MAX - dp[j-nums[i]]) {
if (j >= nums[i]) {
dp[j] += dp[j-nums[i]];
}
}
}
return dp[target];
}
可以看到和零钱兑换II的遍历方式只是内外层循环调了个个而已，最终得到的一个是组合数，一个是排列数。怎么理解呢？
首先先假定nums=[1, 2, 3]，target=4。
然后我们来看零钱兑换得到的组合数，外层循环遍历的是nums的内容，也就是说，每个nums[i]数值都只会进行遍历一次，也就是说对于某个target来说，只会选择一次该数值nums[i]，所以最终得到的结果一定是按照nums[i]遍历顺序得到的结果，也就说会得到[1, 1, 2]的组合结果，而不会出现[2, 1, 1]的组合结果，因为外层遍历是从nums[0]到nums[2]遍历的。
相应的，在组合遍历的过程中，是将nums的遍历移到内层循环中去了。所以对于每个target来说，那么它都有可能取到nums[0]~nums[2]的数，也就是可能取到的是[1, 1, 2]，也有可能取到的是[2, 1, 1]。
以上我们可以得到结论：
题目说明：给定一个字符串和单词数组，问这个字符串是否可以被单词数组构成。
举例说明：s="applepenapple"，wordDict=["apple", "pen"]，显然是可以的。返回true的结果。
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<bool> dp(s.size() + 1); // dp[i] 表示的是前i个字符能不能被wordDict组成
dp[0] = true; // 0个字符的话默认为可以，作为起始条件
for (int i = 1; i <= s.size(); i++) {
for (int j = 0; j < i; j++) {
string str = s.substr(j, i-j);
if (dp[j] == true && wordSet.find(str) != wordSet.end()) {
dp[i] = true;
break;
}
}
}
return dp[s.size()];
}
题目说明：给定一个数值，问组成这个数的完全平方数的最少个数。其中1，4，9，16...是完全平方数
举例说明：n = 12 ，那么它可以等于 4 + 4 + 4，可以看到最少组成12的完全平方数的数量是3个。
这个题目也很好转换成背包问题，这里我们看到数值大小n可以看成背包容量，然后物品是完全平方数，每个数可以取多次也就是完全背包问题了。这样子代码就容易写出了。
int numSquares(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
// 注意这里是将物品放到内层循环的
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = min(dp[i], dp[i - j*j]+1);
}
}
return dp[n];
}
参考文章
