代码随想录算法训练营第46期Day43

leetcode.322零钱兑换

class Solution {
public:
//无限个硬币->完全背包int coinChange(vector<int>& coins, int amount) {vector<int> dp(10010,INT_MAX);//dp代表的在某个数值下最小的硬币数，要求是最小的硬币数，所以初始值要尽可能大/*dp[j]：凑足总额为j所需钱币的最少个数为dp[j]凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);*/dp[0]=0;// for(int i=0;i<=amount;i++){//     for(int j=0;j<coins.size();j++){//         if(i-coins[j]>=0&&INT_MAX!=dp[i-coins[j]])dp[i]=min(dp[i],dp[i-coins[j]]+1);//     }// } for(int j=0;j<coins.size();j++){//这里循环在内在外无所谓for(int i=coins[j];i<=amount;i++){if(INT_MAX!=dp[i-coins[j]])dp[i]=min(dp[i],dp[i-coins[j]]+1);//要求最小的硬币数自然要用min}}if(dp[amount]==INT_MAX) return -1;return dp[amount];}
};

leetcode.279.完全平方数

class Solution {
public:int numSquares(int n) {//这道题和上一道题是一样的vector<int> dp(10010,INT_MAX);vector<int> nums(10010);//这里但开一个数组进行计算会超时// for(int i=0;i<150;i++){//     nums[i]=i*i;// }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];}
};

leetcode.139.单词拆分

回溯法

class Solution {
public:
// 检查起始索引 startIndex 是否大于或等于字符串 s 的长度。如果是，说明整个字符串已经被成功分割，返回 true。
// 从起始索引开始，尝试不同的子字符串长度。
// 对于每个子字符串，检查它是否在单词集合 wordSet 中。
// 如果在，递归地调用 backtracking 函数，从当前子字符串的末尾索引开始。
// 如果递归调用返回 true，说明找到了一种分割方式，返回 true。
// 如果所有可能的子字符串都无法分割字符串，返回 false。bool backtracking(string s,unordered_set<string>& wordSet,int startIndex, vector<bool>& memory){if(startIndex>=s.size()){return true;}
//             使用memory叫做记忆化递归
// 使用memory数组保存每次计算的以startIndex起始的计算结果，如果memory[startIndex]里已经被赋值了，直接用memory[startIndex]的结果。// 如果memory[startIndex]不是初始值了，直接使用memory[startIndex]的结果if (!memory[startIndex]) return memory[startIndex];for (int i = startIndex; i < s.size(); i++) {string word = s.substr(startIndex, i - startIndex + 1);if (wordSet.find(word) != wordSet.end() && backtracking(s, wordSet, i + 1,memory)) {return true;}}memory[startIndex] = false;//说明这个start已经使用过了，下次遇到直接返回他的结果就可以了return false;}bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> word(wordDict.begin(),wordDict.end());vector<bool> memory(s.size(), 1); return backtracking(s,word,0,memory);}
};

动态规划

拿 s = "applepenapple", wordDict = ["apple", "pen"] 举例。

"apple", "pen" 是物品，那么我们要求 物品的组合一定是 "apple" + "pen" + "apple" 才能组成 "applepenapple"。

"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的，那么我们就是强调物品之间顺序。

所以说，本题一定是 先遍历 背包，再遍历物品。

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> words(wordDict.begin(),wordDict.end());vector<bool> dp(10010,false);dp[0]=true;
//         如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
// 所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。for(int i=0;i<=s.size();i++){for(int j=0;j<i;j++){string word = s.substr(j, i - j); //substr(起始位置，截取的个数)if (words.find(word) != words.end() && dp[j]) {dp[i] = true;break;//原来的代码没有break,其实只要dp[i]可以为true就可以停止了}}}return dp[s.size()];}
};