本文主要是介绍第四十六天 | 279.完全平方数 139.单词拆分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：279.完全平方数
本题比较简单，几天没做背包但是这道题很快ac了
尝试解答：
题目类型：给定一个背包容量，求装满背包的最少物品数，且每个物品可以放多次，完全背包
1.dp[j]数组含义：装满容量为 j 的背包所需要的物品数为dp[j]
2.状态转移方程：dp[j] = min(dp[j], dp[j - i * i] + 1)
3.初始化：dp[0] = 0（这个是通过测试集试出来的），0之外的位置初始化为最大值，防止将答案覆盖
4.遍历顺序：必须先遍历背包，在物品的终止条件中会用到背包容量作为限制。如果先遍历物品，那不知道for在哪里终止。
5.打印dp
class Solution {
public:int numSquares(int n) {vector<int> dp(n + 1, INT_MAX); //0之外的位置初始化为最大值，防止将答案覆盖dp[0] = 0;for(int j = 0; j <= n; j++){ //先背包后物品for(int i = 1; i <= n && i * i <= j; i++){ //for循环的判断条件里要多一条平方数小于背包容量，防止访问越界dp[j] = min(dp[j], dp[j - i * i] + 1); //统计方法数}}return dp[n];}
};
其实先遍历物品后遍历背包也可以，只不过要加上一个防止访问越界的判断条件if
题目：139.单词拆分
尝试：失败
这道题相当于是判断给定容量的背包能不能装满。背包总容量s.size()
这个背包的总容量为s.size()，如果到最后背包内所装物品的数量为s.size()，就返回true，否则返回false.
1.dp[j]含义：容量为j的背包所装物品的数目
2.动态转移方程：如果字典里有[i]，dp[j] = dp[j - ] + 1;
3.初始化：dp[0] =
4.遍历顺序：先后顺序没有影响，背包的顺序从小到大
正解：
本题应该是求排列数类型
1.dp数组含义：字符串的长度为 i，能否能装满
2.递推公式：截取[i , j]这一段的s，判断这个子串是否存在于字典中，先将数组字典转化为set,set中查询的函数为find()。if([i，j] && dp[i] == true) 则 dp[j] == true; else dp[j] == false
3.初始化：dp[0] = true，非零下标都为false
4.遍历顺序：求排列数，先遍历背包再物品
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 j = 0; j <= s.size(); j++){ //先背包for(int i = 0; i <= j; i++){string word = s.substr(i, j - i); //将s进行剪切赋值给str//substr(起始位置，截取的个数)if(wordSet.find(word) != wordSet.end() && dp[i] == true){dp[j] = true;}}}return dp[s.size()];}
};[易错]：if的判断条件里应该是dp[i] == true，因为要判断的是i之前的字符串是否查询成功了，不要惯性思维写dp[j - i] == true。
[注意]：各种语法：比如转字典、字典查询、切割字符串等
这篇关于第四十六天 | 279.完全平方数 139.单词拆分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
