【蓝桥杯速成】| 18.完全背包（训练室）
标题一：完全平方数题目描述
279. 完全平方数 - 力扣（LeetCode）
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值即是另一个整数的平方；换句话说，其值即是一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
<strong>输入：</strong>n = 12
<strong>输出：</strong>3
<strong>解释：</strong>12 = 4 + 4 + 4 示例 2：
<strong>输入：</strong>n = 13
<strong>输出：</strong>2
<strong>解释：</strong>13 = 4 + 9 提示：
[*]1 <= n <= 104
解题步骤
参照昨天写的零钱兑换思路，我们不难写出如下代码：
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1,INT_MAX);
dp=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
int k=i*i;
if(j>=k){
dp=min(dp,dp+1);
}
}
}
return dp;
}
}; i代表可选数字，k代表i所盘算出的完全平方数，j代表背包涵量
初始化数组为INT_MAX便于求最小值
dp=0,特别设置为0，便于后续使用、盘算
遍历数字，挨个尝试，更新数组
不放入当前数字则dp值不变，放入则减去占用容量，加上1，
为了选取最小值用min函数在上面两种环境中取小
最后输入dp即可
提交后发现用时很长，才意识到遍历条件上可以优化一下
我们要求和为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;
for(int i=1;i*i<=n;i++){
for(int j=i*i;j<=n;j++){
dp=min(dp,dp+1);
}
}
return dp;
}
}; 标题二：单词拆分
题目描述
139. 单词拆分 - 力扣（LeetCode）
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。假如可以使用字典中出现的一个或多个单词拼接出 s 则返回 true。
留意：不要求字典中出现的单词全部都使用，而且字典中的单词可以重复使用。
示例 1：
<strong>输入:</strong> s = "leetcode", wordDict = ["leet", "code"]
<strong>输出:</strong> true
<strong>解释:</strong> 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
示例 2：
<strong>输入:</strong> s = "applepenapple", wordDict = ["apple", "pen"]
<strong>输出:</strong> true
<strong>解释:</strong> 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意，你可以重复使用字典中的单词。
示例 3：
<strong>输入:</strong> s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
<strong>输出:</strong> false
提示：
[*]1 <= s.length <= 300
[*]1 <= wordDict.length <= 1000
[*]1 <= wordDict.length <= 20
[*]s 和 wordDict 仅由小写英文字母组成
[*]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.length();
if(s.substr(j,len)==wordDict){//与当前单词匹配
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表示当前长度的字符串是否能在字典中找到单词拼接
最后必要返回的就是dp到底为true还是false
vector<string> dp(n+1,false);//n表示s的长度
2.初始化
dp=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 == true && word==s.substr(j-len,len)){
dp=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 = true; // 空字符串可以被表示
for (int j = 1; j <= n; j++) {
for (const string& word : wordDict) {
int len = word.length();
if (j >= len && dp && s.substr(j - len, len) == word) {
dp = true;
break; // 找到一个匹配即可
}
}
}
return dp;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]