0. 起源
0-1背包：最大最小问题
概念：一共有N件物品，第
i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？思路：定义一个二维数组
dp存储最大价值，其中dp[i][j]表示前i件物品体积不超过j的情况下能达到的最大价值。设第i件物品体积为w，价值为v，根据第i件物品是否添加到背包中，可以分两种情况讨论：- 第
i件物品没添加到背包，总体积不超过j的前i件物品的最大价值就是总体积不超过j的前i-1件物品的最大价值，$dp[i][j] = dp[i-1][j]$ - 第
i件物品添加到背包中，$dp[i][j] = dp[i-1][j-w[i]] + v[i]$
- 第
状态转换方程：$dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]) , j >= w[i]$
源代码：
// w 表示背包总体积 // weights 表示物体的重量 // values 表示物体的价值，和 weights 一一对应 int backpack(int w, vector<int> &weights, vector<int> &values) { int n = weights.size(); vector<vector<int>> dp(n, vector<int>(w)) for(int i = 0; i < n; ++ i) { for (int j = 0; j < w; ++ j) { if (j >= w[i]) { // 背包承受力足够放下第 i 个物体 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]); } else { // 背包承受力不够放下第 i 个物体 dp[i][j] = dp[i-1][j]; } } } return dp[n-1][w-1]; }最后：可以优化一下空间的，这里不细说了，注意第二个循环需要倒叙遍历，具体参考：CyC2018
完全背包问题
概念：和0-1背包问题相似，只是每个重量的物体有无数多个，也就可以重复放某个价值的物体，最终目的就是让背包的总价值最大
思路：总体思想和0-1背包一样
- 第
i件物品没添加到背包，同上，$dp[i][j] = dp[i-1][j]$ - 第
i件物品添加到背包中，此时和01背包不太一样，因为每种物品有无限个（但注意书包限重是有限的），所以此时不应该转移到dp[i−1][j−w[i]]而应该转移到dp[i][j−w[i]]，即装入第i种商品后还可以再继续装入第种商品。$dp[i][j] = dp[i][j-w[i]] + v[i]$
- 第
状态转换方程：$dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i]) , j >= w[i]$
源代码：
// w 表示背包总体积 // weights 表示物体的重量 // values 表示物体的价值，和 weights 一一对应 int backpack(int w, vector<int> &weights, vector<int> &values) { int n = weights.size(); vector<vector<int>> dp(n, vector<int>(w)) for(int i = 0; i < n; ++ i) { for (int j = 0; j < w; ++ j) { if (j >= w[i]) { // 背包承受力足够放下第 i 个物体 dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]); } else { // 背包承受力不够放下第 i 个物体 dp[i][j] = dp[i-1][j]; } } } return dp[n-1][w-1]; }同理可以优化空间，好像需要注意：第二个循环正序遍历，不太懂，具体参考完全背包-知乎
多重背包问题
- 先不整理了，有点费脑子
混合背包或者多维度背包
- 太难了，🤮了，具体可以参考九讲背包问题
1. LeetCode实战
参考：力扣-澜山
0. 组合问题
dp[i] += dp[i-num]
// 组合问题需考虑元素之间的顺序，需将target放在外循环，将nums放在内循环
for i in range(1, target+1):
for num in nums:377.组合总和 Ⅳ、494.目标和、518.零钱兑换 II
这里展示一下377.组合总和 Ⅳ，这是需要考虑每个数字之间的顺序的，所以是组合问题
- 用 dp[x] 表示选取的元素之和等于 x的方案数，目标是求 **dp[target]**。
- 动态规划的边界是dp[0]=1，有当不选取任何元素时，元素之和才为 0，因此只有 1 种方案。
- 当$1 <= i <= target$，如果存在一种排列，其中的元素之和等于 i，则该排列的最后一个元素一定是数组 nums 中的一个元素，假设该排列的最后一个元素是 num，则一定有$num <= i$，对于元素之和等于 i−num的每一种排列，在最后添加 num之后即可得到一个元素之和等于 i 的排列，因此在计算 dp[i]**时，应该计算所有的 **dp[i−num] 之和。
- 参考：力扣官方-题解
class Solution { public: int combinationSum4(vector<int>& nums, int target) { vector<unsigned long long> dp(target + 1); dp[0] = 1; for (int i = 1; i <= target; ++ i) { for (auto num: nums) { if (i >= num ) { dp[i] += dp[i-num]; } } } return dp[target]; } };说明一下：这里使用unsigned long long是为了防止测试数据的溢出，其实这个测试用例有点内个，我的疑问解答
1. True、False问题公式
dp[i] = dp[i] or dp[i-num]139.单词拆分、416.分割等和子集
这里展示139.单词拆分：dp[i] 表示 s 的前 i 位是否可以用 wordDict 中的单词表示
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { vector<bool> dp(s.size() + 1); // 这里使用set容器是为方便查找 unordered_set<string> m(wordDict.begin(), wordDict.end()); dp[0] = true; int maxL = 0; // 这里做一个优化，每次j不需要从0开始遍历，wordDict里面有一个最小长度的串 for (auto s: wordDict) { maxL = max(maxL, (int)s.length()); } for (int i = 1; i <= s.size(); ++ i) { int start = max(i - maxL, 0); for (int j = start; j < i; ++ j) { if (dp[j] && m.find(s.substr(j, i-j)) != m.end()) { dp[i] = true; break; } } } return dp[s.size()]; } };
2. 最大最小问题
dp[i] = min(dp[i], dp[i-num]+1) or dp[i] = max(dp[i], dp[i-num]+1)474.一和零、322.零钱兑换
这里展示322.零钱兑换：让找的零钱数最少
假设
f(n)代表要凑齐金额为 n 所要用的最少硬币数量，那么有：$f(n) = min(f(n - c1), f(n - c2), … f(n - cn)) + 1$
其中
c1 ~ cn为硬币的所有面额。再具体解释一下这个公式吧，例如这个示例：
输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1题目求的值为
f(11)，第一次选择硬币时我们有三种选择。假设我们取面额为 1 的硬币，那么接下来需要凑齐的总金额变为
11 - 1 = 10，即f(11) = f(10) + 1，这里的+1就是我们取出的面额为 1 的硬币。同理，如果取面额为 2 或面额为 5 的硬币可以得到：
f(11) = f(9) + 1f(11) = f(6) + 1
所以：
f(11) = min(f(10), f(9), f(6)) + 1参考：力扣-江不知
class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; // 两种遍历方式都可以 for (int i = 1; i <= amount; ++ i) { for (auto c: coins) { if (i >= c && dp[i-c] != INT_MAX) { dp[i] = min(dp[i], dp[i-c] + 1); } } } // for (int c: coins) { // for(int j = c; j <= amount; ++ j) { // if(dp[j- c] != INT_MAX) { // dp[j] = min(dp[j], dp[j-c] + 1); // } // } // } return dp[amount] == INT_MAX ? -1 : dp[amount]; } };
2. Trick
参考：力扣-澜山
不过好像不是很理解，🤒
背包问题技巧：
如果是0-1背包，即数组中的元素不可重复使用，nums放在外循环，target在内循环，且内循环倒序；
for num in nums: for i in range(target, nums-1, -1):
如果是完全背包，即数组中的元素可重复使用，nums放在外循环，target在内循环。且内循环正序。
for num in nums: for i in range(nums, target+1):
如果组合问题需考虑元素之间的顺序，需将target放在外循环，将nums放在内循环。
for i in range(1, target+1): for num in nums:
