6. 完全平方数（LeetCode-279）
题目
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12 输出：3 解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13 输出：2 解释：13 = 4 + 9
提示：
1 <= n <= 104
思路
看到示例一的 4 + 4 + 4 4+4+44+4+4 知道是完全背包问题，本题求和为 n 的完全平方数的最少数量
五部曲
dp[j] 含义
和为 j jj 的完全平方数的最少数量
递推公式
想一下，如果访问的当前物品是完全平方数，那么就分别求装它和不装它的数量，二者取小值。如果不是完全平方数，那么还是取不装它的数量
d p [ j ] = m i n ( d p [ j ] , d p [ j − i ] + 1 ) dp[j]=min(dp[j],dp[j-i]+1)
dp[j]=min(dp[j],dp[j−i]+1)
数组初始化
和为 0 00 的完全平方数的最少数量肯定为零，而其他要初始化为最大值
遍历顺序
这里求最少数量，是组合数还是排列数都无所谓，所以顺序随意
代码展示
class Solution { public: int numSquares(int n) { vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for (int i = 1; i <= n; i++) { bool flag = false; if (i == 1) { flag = true; } for (int k = 0; k < i; k++) { if (k * k == i) { flag = true; break; } } for (int j = i; j <= n; j++) { if (flag && dp[j - i] != INT_MAX) { dp[j] = min(dp[j], dp[j - i] + 1); } } } return dp[n]; } };
分析一下，很快写出来了。但时间复杂度过于之高。那肯定是求完全平方数没有处理好。看了下题解，是我的物品选错了，我是遍历数然后判断它是不是完全平方数，但这样做就烦了。数值 n 什么时候完全平方数？说白了 n是整数。那我的物品就取 n
class Solution { public: int numSquares(int n) { vector<int> dp(n + 1, INT_MAX); dp[0] = 0; for (int i = 1; i * i <= n; i++) { for (int j = i * i; j <= n; j++) { dp[j] = min(dp[j], dp[j - i * i] + 1); } } return dp[n]; } };
7. 单词拆分（LeetCode-139）
题目
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
提示：
1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s 和 wordDict[i] 仅有小写英文字母组成
wordDict 中的所有字符串 互不相同
思路
不会，卡尔哥的也没看懂。然后发现官方题解很清晰
我们定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串s[0~i−1] 是否能被空格拆分成若干个字典中出现的单词。从前往后计算考虑转移方程，每次转移的时候我们需要枚举包含位置 i-1 的最后一个单词，看它是否出现在字典中以及除去这部分的字符串是否合法即可。公式化来说，我们需要枚举 s[0~i-1] 中的分割点 j ，看 s[0~j-1] 组成的字符串 S 1 S_1（默认 j = 0 时 S 1为空串）和 s[j~i-1] 组成的字符串 S 2 是否都合法，如果两个字符串均合法，那么按照定义 S 1 和 S 2 拼接成的字符串也同样合法。由于计算到 dp[i] 时我们已经计算出了 dp[0~i−1] 的值，因此字符串 S 1 是否合法可以直接由 dp[j] 得知，剩下的我们只需要看 S 2是否合法即可，因此我们可以得出如下转移方程
d p [ i ] = d p [ j ] & & c h e c k ( s [ j ∼ i − 1 ] )
五部曲
dp[i] 含义
表示字符串前 i 个字符组成的字符串s[0~i−1] 是否能被空格拆分成若干个字典中出现的单词
递推公式
d p [ i ] = d p [ j ] & & c h e c k ( s [ j ∼ i − 1 ] )
数组初始化
dp[0]=true 表示字符串为空，但题目中说了“给定⼀个非空字符串 s” 所以测试数据中不会出现i为0的情况，那么dp[0]初始为true完全就是为了推导公式。下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为⼀个或多个在字典中出现的单词。
遍历顺序
实在是没看懂，直接复制卡尔哥的原话了
题⽬中说是拆分为⼀个或多个在字典中出现的单词，所以这是完全背包。
还要讨论两层for循环的前后循序。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
本题最终要求的是是否都出现过，所以对出现单词集合⾥的元素是组合还是排列，并不在意！
那么本题使⽤求排列的⽅式，还是求组合的⽅式都可以。
即：外层for循环遍历物品，内层for遍历背包 或者 外层for遍历背包，内层for循环遍历物品 都是可以的。
但本题还有特殊性，因为是要求⼦串，最好是遍历背包放在外循环，将遍历物品放在内循环。如果要是外层for循环遍历物品，内层for遍历背包，就需要把所有的⼦串都预先放在⼀个容器⾥。（如果不理解的话，可以⾃⼰尝试这么写⼀写就理解了）所以最终我选择的遍历顺序为：遍历背包放在外循环，将遍历物品放在内循环。内循环从前到后。
测试用例
代码展示
class Solution { public: bool wordBreak(string s, vector<string> &wordDict) { unordered_set<string> wordset(wordDict.begin(), wordDict.end()); vector<bool> dp(s.size() + 1, false); dp[0] = true; for (int i = 0; i <= s.size(); i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordset.find(s.substr(j, i - j)) != wordset.end()) { dp[i] = true; break; } } } return dp[s.size()]; } };
多重背包
LeetCode上无对应题目，只简单介绍
1. 多重背包例题
题目
有N种物品和一个容量为 V 的背包。第i种物品最多有 M i 件可用，每件耗费的空间是 C i ，价值是 W i 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
多重背包和01背包是非常像的， 为什么和01背包像呢？
每件物品最多有 M i 件可用，把 M i 件摊开，其实就是一个01背包问题了。
例如：
背包最大重量为10。
物品为：
| 重量 | 价值 | 数量 | |
| 物品0 | 1 | 15 |
2 |
| 物品1 | 3 |
20 |
3 |
| 物品2 | 4 |
30 |
2 |
问背包能背的物品最大价值是多少？
和如下情况有区别么？
| 重量 | 价值 | 数量 | |
| 物品0 | 1 |
15 |
1 |
| 物品0 | 1 |
15 |
1 |
| 物品1 | 3 |
20 |
1 |
| 物品1 | 3 |
20 |
1 |
| 物品1 | 3 |
20 |
1 |
| 物品2 | 4 |
30 |
1 |
| 物品2 | 4 |
30 |
1 |
毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。
思路
将有多件的物品展开，就可将完全背包转换成01背包
代码展示
#include <iostream> #include <vector> using namespace std; void test_multi_pack() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; vector<int> nums = {2, 3, 2}; int bagWeight = 10; for (int i = 0; i < nums.size(); i++) { while (nums[i] > 1) { // nums[i]保留到1，把其他物品都展开 weight.push_back(weight[i]); value.push_back(value[i]); nums[i]--; } } vector<int> dp(bagWeight + 1, 0); for (int i = 0; i < weight.size(); i++) { // 遍历物品 for (int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } for (int j = 0; j <= bagWeight; j++) { cout << dp[j] << " "; } cout << endl; } cout << dp[bagWeight] << endl; } int main() { test_multi_pack(); return 0; }
小结
做了这些题目后，感觉在没有系统学习dp之前，抓不住重点，有时稀里糊涂ac了，但不能完整推出来。所以说，卡尔哥的专题真的很有帮助！
