代码随想录算法训练营第四十五天|139.单词拆分

139.单词拆分

转化为背包问题：

单词就是物品，字符串s就是背包

动规五部曲

确定dp数组以及下标的含义

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词

确定递推公式

如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true

dp[i] = true

dp数组初始化

dp[0]初始为true

确定遍历顺序

先遍历 背包，再遍历物品

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(inti=1;i<=s.size();i++){// 遍历背包for(intj=0;j<i;j++){// 遍历物品string word=s.substr(j,i-j);//substr(起始位置，截取的个数)if(wordSet.find(word)!=wordSet.end()&&dp[j]){dp[i]=true;}}}returndp[s.size()];}