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()];}
