动态规划
背包问题
背包问题是一类经典的动态规划问题，它非常灵活，需要仔细琢磨体会，本文先对背包问题的几种常见类型作一个总结，期望可以用一套框架解决背包问题。 常见背包问题可分为：
-
01 背包问题：
最基本的背包问题就是 01 背包问题：一共有 N 件物品，第 i（i 从 1 开始）件物品的重量为 w[i]，价值为 v[i]。在总重量不超过背包承载上限 W 的情况下，能够装入背包的最大价值是多少？ -
完全背包问题：
完全背包与 01 背包不同就是每种物品可以有无限多个：一共有 N 种物品，每种物品有无限多个，第 i（i 从 1 开始）种物品的重量为 w[i]，价值为 v[i]。在总重量不超过背包承载上限 W 的情况下，能够装入背包的最大价值是多少？ 可见 01 背包问题与完全背包问题主要区别就是物品是否可以重复选取。
背包问题具备的特征：
是否可以根据一个 target（直接给出或间接求出），target 可以是数字也可以是字符串，再给定一个数组 arrs，问：能否使用 arrs 中的元素做各种排列组合得到 target。
背包问题解法：
- 01 背包问题：
如果是 01 背包，即数组中的元素不可重复使用，外循环遍历 arrs，内循环遍历 target，且内循环倒序:
完全背包问题：
（1）如果是完全背包，即数组中的元素可重复使用并且不考虑元素之间顺序，arrs 放在外循环（保证 arrs 按顺序），target在内循环。且内循环正序。 （2）如果组合问题需考虑元素之间的顺序，需将 target 放在外循环，将 arrs 放在内循环，且内循环正序。
- 例题：
01 背包问题
- 分割等和子集
本题要求把数组分成两个等和的子集，相当于找到一个子集，其和为 sum / 2，这个 sum / 2 就是 target（target 间接给出）。 于是转化为是否可以用 nums 中的数组合和成 target，01 背包问题，外层循环为选择池 num: nums，内层循环为 target。
dp[i] 表示是否存在和为 i 的 num 组合。
外层遍历 nums 每个 num；
内层遍历 target（由大到小）。
对于元素之和等于 i - num 的每一种组合，在最后添加 num 之后即可得到一个元素之和等于 i 的组合，因此dp[i] 依赖于 dp[i - num]，并且在计算 dp[i - num] 时，要保证索引较小的元素值不被覆盖，需要后向更新 dp[i]，并且当 i - num < i 时， dp[i] 已经更新过，于是： dp[i] = dp[i] || dp[i - num] 对于特例：如果 sum 为奇数，那一定找不到符合要求的子集，返回 False。 对于边界条件，我们定义 dp[0] = true 表示当 i - num = 0，存在一个 num 和为 i。 最后返回 dp[target]。
class Solution {
public:
bool canPartition(vector<int>& nums) {
int len = nums.size();
int sum = 0;
for (int num: nums) {
sum += num;
}
if ((sum & 1) == 1) {
return false;
}
int target = sum / 2;
vector<bool> dp(target + 1);
dp[0] = true;
for(int num: nums){
for(int i = target; i >= num; i--){
dp[i] = dp[i] || dp[i - num];
}
}
return dp[target];
}
};
复杂度分析：
时间复杂度：O(target × n)，其中 n 是数组 nums 的长度。
空间复杂度：O(target)。
494. 目标和
我们想要的 S = 正数和 - 负数和 = x - y 而已知 x 与 y 的和是数组总和：x + y = sum 可以求出 x = (S + sum) / 2 = target 也就是我们要从 nums 数组里选出几个数，令其和为 target（target 间接给出）。 于是转化为是否可以用 nums 中的数组合和成 target，01 背包问题，外层循环为选择池 nums，内层循环为 target。 dp[i] 表示和为 i 的 num 组合有 dp[i] 种。
外层遍历 nums 每个 num；
内层遍历 target（由大到小）。
对于元素之和等于 i - num 的每一种排列，在最后添加 num 之后即可得到一个元素之和等于 i 的排列，因此在计算 dp[i] 时，应该计算所有的 dp[i − num] 之和。 dp[i] = dp[i] + dp[i - num] 对于边界条件，我们定义 dp[0] = 1 表示只有当不选取任何元素时，元素之和才为 0，因此只有 1 种方案。 最后返回 dp[target]
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int sum = 0;
for(int num : nums) sum += num;
if(S > sum || (S + sum) % 2 == 1) return 0;
int target = (S + sum) / 2;
vector<int> dp(target + 1);
dp[0] = 1;
for(int num : nums){
for(int i = target; i >= num; i--){
dp[i] = dp[i] + dp[i - num];
}
}
return dp[target];
}
};
复杂度分析：
时间复杂度：O(target × n)，其中 n 是数组 nums 的长度。
空间复杂度：O(target)。
完全背包问题
139. 单词拆分
转化为是否可以用 wordDict 中的词组合成 s，完全背包问题，并且为“考虑排列顺序的完全背包问题”，外层循环为 target ，内层循环为选择池 wordDict。 dp[i] 表示以 i 结尾的字符串是否可以被 wordDict 中组合而成。
外层遍历 s 中每一个与 word 同长度的字串 s.substr(i - sz, sz) ；
内层遍历 wordDict 每个 word。
判断 s.substr(i - sz, sz) == word： （1）若不相等，说明与该 word 不匹配，继续遍历； （2）若相等，说明从 [i - sz] 到 i 的字符与 word 匹配。 dp[i] = dp[i] || d[[i - sz]] 对于边界条件，我们定义 dp[0] = true 表示空串且合法。 最后返回 dp[s.size()]
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp(s.size() + 1);
dp[0] = true;
for(int i = 1; i <= s.size(); i++){
for(auto& word: wordDict){
int sz = word.size();
if (i - sz >= 0 && s.substr(i - sz, sz) == word)
dp[i] = dp[i] || dp[i - sz];
}
}
return dp[s.size()];
}
};
复杂度分析
时间复杂度：O(target × n)，其中 n 是数组 nums 的长度。
空间复杂度：O(target)。
279. 完全平方数 我们想要的 S = 若干个完全平方数的和 完全平方数最小为 1，最大为 sqrt(n) 也就是我们要从 nums = [1, 2, ..., sqrt(n)] 数组里选出几个数，令其平方和为 target = n。 于是转化为是否可以用 nums 中的数组合和成 target，完全背包问题，外层循环为选择池 nums，内层循环为 target。 dp[i] 表示和为 i 的 nums 组合中完全平方数最少有 dp[i] 个。
外层遍历 nums 每个 num；
内层遍历 n。
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1, INT_MAX);;
dp[0]=0;
for(int num = 1; num <= sqrt(n); num++){
for(int i = 0; i <= n; i++){
if(i >= num * num)
dp[i] = min(dp[i], dp[i - num * num] + 1);
}
}
return dp[n];
}
};
对于元素之和等于 i - num * num 的每一种组合，在最后添加 num 之后即可得到一个元素平方和等于 i 的组合，因此在计算 dp[i] 时，应该计算所有的 dp[i − num * num] + 1 中的最小值。 dp[i] = min(dp[i], dp[i - num * num] + 1) 对于边界条件，我们定义 dp[0] = 0。 最后返回 dp[n]
复杂度分析
时间复杂度：O(n x sqrt{n})，在主步骤中，我们有一个嵌套循环，其中外部循环是 n 次迭代，而内部循环最多需要 sqrt{n} 迭代。
空间复杂度：O(n)，使用了一个一维数组 dp。
322. 零钱兑换
转化为是否可以用 coins 中的数组合和成 amount，完全背包问题，并且为“不考虑排列顺序的完全背包问题”，外层循环为选择池 coins，内层循环为 amount。 dp[i] 表示和为 i 的 coin 组合中硬币最少有 dp[i] 个。
外层遍历 coins 每个 coin；
内层遍历 amount。
对于元素之和等于 i - coin 的每一种组合，在最后添加 coin 之后即可得到一个元素之和等于 i 的组合，因此在计算 dp[i] 时，应该计算所有的 dp[i − coin] + 1 中的最小值。 dp[i] = min(dp[i], dp[i - coin] + 1) 对于边界条件，我们定义 dp[0] = 0。 最后返回 dp[amount]
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<long long> dp(amount+1, INT_MAX);
dp[0] = 0;
for(int& coin: coins){
for(int i = 0; i <= amount; i++){
if(coin <= i)
dp[i] = min(dp[i], dp[i-coin] + 1);
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
};
复杂度分析：
时间复杂度：O(amount x n)，其中 n 为 coins 大小
空间复杂度：O(amount)
377. 组合总和 Ⅳ
转化为是否可以用 nums 中的数组合和成 target，完全背包问题，并且为“考虑排列顺序的完全背包问题”，外层循环为 target ，内层循环为选择池 nums。 dp[i] 表示和为 i 的 num 组合有 dp[i] 种。
外层遍历 target；
内层遍历 nums 每个 num。
对于元素之和等于 i - num 的每一种排列，在最后添加 num 之后即可得到一个元素之和等于 i 的排列，因此在计算 dp[i] 时，应该计算所有的 dp[i − num] 之和。 dp[i] = dp[i] + dp[i - num] 对于边界条件，我们定义 dp[0] = 1 表示只有当不选取任何元素时，元素之和才为 0，因此只有 1 种方案。 最后返回 dp[target]
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1);
dp[0] = 1;
for(int i = 1; i <= target; i++){
for(int& num: nums){
if(num <= i && dp[i - num] < INT_MAX - dp[i])
dp[i] += dp[i - num];
}
}
return dp[target];
}
};
复杂度分析：
时间复杂度：O(target x n)，其中 n 为 wordDict 大小
空间复杂度：O(target)
518. 零钱兑换 II 转化为是否可以用 coins 中的数组合和成 amount，完全背包问题，并且为“不考虑排列顺序的完全背包问题”，外层循环为选择池 coins，内层循环为 amount。 dp[i] 表示和为 i 的 coin 组合有 dp[i] 种。
外层遍历 coins 每个 coin；
内层遍历 amount。
对于元素之和等于 i - coin 的每一种组合，在最后添加 coin 之后即可得到一个元素之和等于 i 的组合，因此在计算 dp[i] 时，应该计算所有的 dp[i − coin] 之和。 dp[i] = dp[i] + dp[i - coin] 对于边界条件，我们定义 dp[0] = 1，表示只有当不选取任何元素时，元素之和才为 0，因此只有 1 种方案。 最后返回 dp[amount]。
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1);
dp[0] = 1;
for(int& coin: coins){
for(int i = 0; i <= amount; i++){
if(coin <= i)
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
};
复杂度分析：
时间复杂度：O(amount x n)，其中 n 为 coins 大小
空间复杂度：O(amount)
转载：
https://leetcode.cn/problems/coin-change-ii/solutions/783992/yi-pian-wen-zhang-chi-tou-bei-bao-wen-ti-2xkk/?envType=study-plan-v2&envId=dynamic-programming
https://leetcode.cn/problems/coin-change-ii/solutions/744156/yi-tao-kuang-jia-jie-jue-bei-bao-wen-ti-6kaze/?envType=study-plan-v2&envId=dynamic-programming