题目一：完全平方数
问题描述
279. 完全平方数 - 力扣（LeetCode）
给你一个整数 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
解题步骤
参照昨天写的零钱兑换思路，我们不难写出如下代码：
class Solution {
public:int numSquares(int n) {vector<int> dp(n+1,INT_MAX);dp[0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=n;j++){int k=i*i;if(j>=k){dp[j]=min(dp[j],dp[j-k]+1);}}}return dp[n];}
};i代表可选数字，k代表i所计算出的完全平方数，j代表背包容量
初始化数组为INT_MAX便于求最小值
dp[0]=0,特别设置为0，便于后续使用、计算
遍历数字，挨个尝试，更新数组
不放入当前数字则dp值不变，放入则减去占用容量，加上1，
为了选取最小值用min函数在上面两种情况中取小
最后输入dp[n]即可
提交后发现用时很长，才意识到遍历条件上可以优化一下
我们要求和为n，那么这个i不需要遍历到n，
不然此时算出k=n*n,远超所需，
所以外层循环应该改为
for(int i=1;i*i<=n;i++)
同时内层的j初始值也应该改变，后续也不需要判断j是否大于等于k
省时又省力
for(int j=i*i;j<=n;j++)
这样就大大减少了无用功
完整代码如下！
code
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];}
};题目二：单词拆分
问题描述
139. 单词拆分 - 力扣（LeetCode）
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 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 <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串 互不相同
解题步骤
看完题目，这题应该是有序的完全背包
但是我先试了一下最简单的逐字匹配
写出的代码如下
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int j=0;
while(j<s.length()){
for(int i=0;i<wordDict.size();i++){//单词
int len=wordDict[i].length();
if(s.substr(j,len)==wordDict[i]){//与当前单词匹配
j=j+len;//下一位！
}
else return false;//失配返回false
}
}
return true;//执行结束返回true
}
};
但这样的代码存在严重的问题
我试图按顺序匹配 wordDict 中的单词，一旦匹配就跳到下一个位置，但这样会忽略其他可能的组合方式。
例如：
s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
可能会先匹配 "cats" 然后 "and"，但剩下的 "og" 无法匹配，直接返回 false，
而实际上正确的组合是 "cat" + "sand" + "dog"。
我没有回溯机制在当前单词不合适的情况下返回尝试其它组合
所以呢
还是走动规五部曲吧！
1.确定dp数组下标及含义
还是使用一维数组dp,
j表示当前待匹配的字符串长度
dp[j]表示当前长度的字符串是否能在字典中找到单词拼接
最后需要返回的就是dp[n]到底为true还是false
vector<string> dp(n+1,false);//n表示s的长度
2.初始化
dp[0]=true
代表空字符串可以被拼接
其它都初始化为false，在初始化时顺手完成了！
3.遍历顺序
由于拼接过程是有序的，所以外层是背包，内层是单词
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
for(int j=1;j<n;j++){//0已经被初始化，从1开始即可
for(const string& word:wordDict){//用迭代器遍历单词更方便
4.递推公式
我们要做的操作是取出已经放入的单词，加入当前遍历到的单词，判断是否匹配
所以要判断
1.当前单词长度j 是否大于等于 待加入单词长度len
不然根本换不了啊！
2.取出后状态是否为true
如果拿出来一个单词，前面拼不起来，那不是白搭
3.加入单词与字符串是否匹配
都要加入肯定得匹配嘛
在以上都符合的情况下，我们才更新dp值为true
否则不做处理
if( j >= len && dp[j-len] == true && word==s.substr(j-len,len)){
dp[j]=true;
break;//找到一个匹配的就结束
}
整理代码即可得到以下完整版！
code
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());int n = s.length();vector<bool> dp(n + 1, false);dp[0] = true; // 空字符串可以被表示for (int j = 1; j <= n; j++) {for (const string& word : wordDict) {int len = word.length();if (j >= len && dp[j - len] && s.substr(j - len, len) == word) {dp[j] = true;break; // 找到一个匹配即可}}}return dp[n];}
};