刷leetcode-hot100-动态规划3.10
刷leetcode hot100–动态规划3.10
继续昨天的完全平方数[13:20]【确实和零钱兑换一脉相承】
前提简要：昨天尝试，没什么想法，本来觉得maybe先求一下sqrt(n)，确定一下阈值【其实也对】
然后不知道怎么求sqrt了？？–>直接调用sqrt(n) 或者 用二分查找
进入正题：
dp[n]表示和为n的完全平方数最小数量
dp[n] = min{dp[n-i*i]+1,dp[n]}
初始化 dp[n]–>INT_MAX
第一版代码问题【编译不过】：1. dp[0]=0 ,要不然dp[1]没法是1， 所以还是要带入代码验算几个dp， dp不能全初始化为INT_MAX/0，要不然没法迭代
2.j<=sqrt(i)，"<="，要不然1没法遍历到完全平方数1；“sqrt(i)”防止i-j*j<0,数组索引不合法
if (dp[i - j * j] != INT_MAX) 防止INT_MAX+1溢出【其实也就是 j <= sqrt(i)】
class Solution {
public:
int numSquares(int n) {
// 完全想不到和动态规划什么关系
// 完全平方数，如何开方
// 和为n的完全平方数最小数量-->dp[n]表示和为n的完全平方数最小数量
// dp[n] = min{dp[n-i*i]+1,dp[n]}但是不会超出时间限制吗
// ？初始化
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
// 遍历
for (int i = 1; i <= n; i++) { // dp[n]
for (int j = 1; j <= sqrt(i); j++) { // j^2 <=e.g.1
// if (dp[i - j * j] != INT_MAX) {
dp[i] = min(dp[i - j * j] + 1, dp[i]);
//}
}
}
return dp[n];
}
};第二题：单词拆分
【回溯：分隔回文串？？？】
回顾：c++中关于字符串的函数
1.s1.substr(2,5); // 结果：23456—–参数2：从s1[2]开始截取，参数5表示：截取多长
s.end()
适用于
标准容器（如
std::string
和
std::vector
）或支持
end()
成员函数的自定义类
set的find返回的也是迭代器，string的find返回的是string首字母下标
题的思路：1.dp[n]表示前n个字符是否可以用已知wordDict表示
2.初始化：dp[0] = true,其他false
3.遍历顺序：排列数–>先遍历背包，再遍历物品【我的初始循环i，更新 i+wordDict[j].size()-1的dp，这个思路比较混乱，虽然也能行的通；
一般思路是更新dp[i]】
初版代码问题：
卒于s =“abcd”；wordDict =[“a”,“abc”,“b”,“cd”]
输出1,3,2，
好吧，为什么呢 ，不理解
我悟了！！！！！
for(int j = 0; j<wordDict.size() && i+wordDict[j].size()-1<=s.size() ;j++){
中
j<wordDict.size() && i+wordDict[j].size()-1<=s.size()
如果for中某一时刻不满足这个条件，for结束循环，退出，即j=1不满足的话，就不会有j=2了
所以正确的做法是：
for(int j = 0; j < wordDict.size(); j++) {
if ((i + wordDict[j].size() - 1) <= s.size()) {
这告诉我们，for的条件里不要塞太多。。。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
//字符串操作
//依旧不知道和动态规划的关系
//看代码随想录说想成背包【s】和物品【wordDict】
//难道不是检验wordDict有没有和s重合的，然后去除,检测重合-->for{for{}} OR s.find("");
//dp[n]表示从本字符串从第一个字符到第n个是否可以由这些单词组成
vector<bool> dp(s.size()+1,false);//bool
dp[0] = true;
//dp[n] = dp[i] && s[i...wordDict[j].size()+i-1].find(wordDict[j])
for(int i = 1;i<=s.size();i++){//第一个字符下标为0
for(int j = 0;j<wordDict.size() && i+wordDict[j].size()-1<=s.size() ;j++){
string sub = s.substr(i-1,wordDict[j].size());
if(sub == wordDict[j]){
if(dp[i-1] == true){
dp[wordDict[j].size()+i-1] = true;
cout<<wordDict[j].size()+i-1<<endl;
}
}
}
}
return dp[s.size()];
}
};比较正常的思路。。 ：
一般dp[n]遍历到n是更新的是dp[n],要不然逻辑太混乱
在实操过程中，i/j/wordDict[j].size()我一直绕不清楚，太绕了……
如果顺应初始化dp（size（），false）会好一点
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
//字符串操作
//依旧不知道和动态规划的关系
//看代码随想录说想成背包【s】和物品【wordDict】
//难道不是检验wordDict有没有和s重合的，然后去除,检测重合-->for{for{}} OR s.find("");
//dp[n]表示从本字符串从第一个字符到第n个是否可以由这些单词组成
vector<bool> dp(s.size()+1,false);//bool
dp[0] = true;
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
//dp[n] = dp[i] && s[i...wordDict[j].size()+i-1].find(wordDict[j])
for(int i = 1;i<=s.size();i++){//第一个字符下标为0
for(int j = 1;j<=i;j++){
//j-1..i-1
string word = s.substr(j-1, i - j +1);
if (wordSet.find(word) != wordSet.end() && dp[j-1]) {
dp[i] = true;
}
}
}
return dp[s.size()];
}
};