139.单词拆分
要求：
有N个字母，一个字符串，看这个字符串是否由这个这些字母组成，注意，这些字母可以用无限次
思路：
无法得知背包的容量怎么设置，刚开始的思路是，让这些字母随意组成任意个字符串，然后查看是否满足
新思路：
从开始节点，到任意节点，查看是否满足N个字母，同时它的开始的地方要满足要求
代码：
1 // 需要二刷回文串 -》需要再刷 排列数和组合数 2 3 // 要求：字符串里面可以选0-N次，拼凑成字符串S 4 // 思路：完全背包问题 5 // 原始dp[N]:当容量为N时，它的最大价值是多少 6 // 7 // 物品：wordDict 8 // 9 // 容量：就是s的长度， 10 // 11 // 可以想象成两个双指针，I走在后面，J走在前面，当J是满足word的要求，且J-i，也满足要求，那么就是满足 12 // 注意：J~I中间有不满足的情况 13 // 14 // 闪光点：如果不知道Word排列多少个才可以满足要求，那么就直接吧被排列的长度作为容器，然后这样去搜索 15 // 16 // dp[n] 当指针到第N个字符的时候，是否在wordDIct中 17 // 18 bool wordBreak(string s, vector<string>& wordDict) { 19 //为了快速查找，将word转成set 20 set<string> wordSet(wordDict.begin(), wordDict.end()); 21 if (s.size() == 1 && wordSet.find(s) == wordSet.end()) return false; 22 23 vector<bool>dp(s.size() + 1, false); 24 dp[0] = true; 25 26 //因为是有排列的顺序，所以是外部 27 for (int j = 0; j < s.size() + 1; j++) 28 { 29 for (int i = j + 1; i < s.size() + 1; i++) 30 { 31 string subStr = s.substr(j , (i - j)); 32 if (wordSet.find(subStr) != wordSet.end() && dp[j]) 33 { 34 dp[i] = true; 35 } 36 37 } 38 } 39 40 for (auto a : dp) 41 { 42 cout << a << " "; 43 } 44 45 return dp[s.size()]; 46 }