起初看到这道题目以为是简单题，考察字符串的操作，每次循环找是否有字串，然后截取直到s为空那么就可以返回true，如果有一次内循环没有找到字串那么直接返回false
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {while(!s.empty()){bool flag=false;for(string str: wordDict){int pos=s.find(str);if(pos!=-1){flag=true;s.erase(pos,str.size());}}if(!flag)return false;}return true;}
};结果发现截取的次序不对是无法通过本例的，说明次序对结果的影响
而对于次序，通过枚举可以发现无非就是对于每一个字典取与不取的情况，那么可以通过回溯解决，而回溯又可以转换为动态规划，所以我改用动态规划来解决，这道题正好也是多重背包问题，只是写法可能稍有不同
背包是s，物品是wordDict，求能否用物品装满这个背包，物品可以重复使用
很容易想到dp[i]为是否能装满这个背包的bool值，而递推公式是dp[j]&&街区的子串在物品当中
由于物品先后顺序对结果有影响，是个排列的问题，所以先遍历背包再遍历物品，这道题目比较特殊不像之前的题目可以直接j-nums[i]，由于是字符串所以通过间接的截取再从字典中寻找
dp[0]初始化为true，表示字符串为空是可以用字典装满
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int n=wordDict.size(),bagWeight=s.size();unordered_set<string> wordSet(wordDict.begin(),wordDict.end());vector<bool> dp(bagWeight+1,false);dp[0]=true;for(int i=1;i<=bagWeight;i++)for(int j=0;j<i;j++){string bg=s.substr(j,i-j);if(wordSet.find(bg)!=wordSet.end()&&dp[j])dp[i]=true;}return dp[bagWeight];}
};
