【蓝桥杯速成】| 18.完全背包（训练室）

标题一：完全平方数

题目描述

279. 完全平方数 - 力扣（LeetCode）
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值即是另一个整数的平方；换句话说，其值即是一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：

1. <strong>输入：</strong>n = 12
2. <strong>输出：</strong>3
3. <strong>解释：</strong>12 = 4 + 4 + 4

复制代码

示例 2：

1. <strong>输入：</strong>n = 13
2. <strong>输出：</strong>2
3. <strong>解释：</strong>13 = 4 + 9

复制代码

提示：

• 1 <= n <= 104
  

解题步骤

参照昨天写的零钱兑换思路，我们不难写出如下代码：

1. class Solution {
2. public:
3.     int numSquares(int n) {
4.         vector<int> dp(n+1,INT_MAX);
5.         dp[0]=0;
6.         for(int i=1;i<=n;i++){
7.             for(int j=0;j<=n;j++){
8.                 int k=i*i;
9.                 if(j>=k){
10.                     dp[j]=min(dp[j],dp[j-k]+1);
11.                 }
12.             }
13.         }
14.         return dp[n];
15.     }
16. };

复制代码

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

1. class Solution {
2. public:
3.     int numSquares(int n) {
4.         vector<int> dp(n+1,INT_MAX);
5.         dp[0]=0;
6.         for(int i=1;i*i<=n;i++){
7.             for(int j=i*i;j<=n;j++){
8.                 dp[j]=min(dp[j],dp[j-i*i]+1);
9.             }
10.         }
11.         return dp[n];
12.     }
13. };

复制代码

---

标题二：单词拆分

题目描述

139. 单词拆分 - 力扣（LeetCode）
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。假如可以使用字典中出现的一个或多个单词拼接出 s 则返回 true。
留意：不要求字典中出现的单词全部都使用，而且字典中的单词可以重复使用。
示例 1：

1. <strong>输入:</strong> s = "leetcode", wordDict = ["leet", "code"]
2. <strong>输出:</strong> true
3. <strong>解释:</strong> 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

复制代码

示例 2：

1. <strong>输入:</strong> s = "applepenapple", wordDict = ["apple", "pen"]
2. <strong>输出:</strong> true
3. <strong>解释:</strong> 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
4.      注意，你可以重复使用字典中的单词。

复制代码

示例 3：

1. <strong>输入:</strong> s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
2. <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[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

1. class Solution {
2. public:
3.     bool wordBreak(string s, vector<string>& wordDict) {
4.         unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
5.         int n = s.length();
6.         vector<bool> dp(n + 1, false);
7.         dp[0] = true; // 空字符串可以被表示
9.         for (int j = 1; j <= n; j++) {
10.             for (const string& word : wordDict) {
11.                 int len = word.length();
12.                 if (j >= len && dp[j - len] && s.substr(j - len, len) == word) {
13.                     dp[j] = true;
14.                     break; // 找到一个匹配即可
15.                 }
16.             }
17.         }
19.         return dp[n];
20.     }
21. };

复制代码

 


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。