动态规划题
令s[i..j]表示下标从i到j的子串，它的所有分割情况用words[i]表示
假设s[0..i]的所有分割情况words[i]已知。则s[0..i+1]的分割情况words[i+1] = words[k] + s[k+1..i+1]，其中（有三个条件要满足）(1) 0 <= k <= i，(2) words[k]非空，(3) s[k+1..i+1]在字典中。
根据这个递推公式求解，有两种枚举方式：
1. 对于每个待求解的位置i，从0到i枚举所有的k，然后检验words[k]是否非空，以及s[k+1..i+1]是否在字典中
2. 对于每个待求解的位置i，枚举字典中的所有单词w，计算出k=i-w.length，然后检验是否0 <= k <= i，以及s[k+1..i+1]和w是否相等
两种方式各有优缺点，如果枚举k，则当原串s特别长的时候，效率比较低；如果枚举字典，当字典里的单词很多的时候，效率比较低。
感觉第一种方式（枚举k）更加自然一些。
最后需要注意的是，最坏情况下枚举的结果是2^n数量级的，此时如果把每个s[0..i]的所有分割情况都保存下来，内存会爆掉。所以只保存s[0..i]分割后的最后一个单词，最后用广搜构造所有解。
代码：
1 vector<string> wordBreak(string s, unordered_set<string> &dict) { 2 map<int, vector<string> > record; 3 int len = s.length(); 4 5 // DP枚举 6 for (int i = 0; i < len; i++) { 7 vector<string> words; 8 9 if (dict.find(s.substr(0, i + 1)) != dict.end()) 10 words.push_back(s.substr(0, i + 1)); 11 12 for (int j = 1; j <= i; j++) { 13 vector<string> pres = record[j - 1]; 14 string post = s.substr(j, i - j + 1); 15 if (!pres.empty() && dict.find(post) != dict.end()) { 16 words.push_back(post); 17 } 18 } 19 20 record.insert(pair<int, vector<string> >(i, words)); 21 } 22 23 // DFS构造 24 vector<string> res; 25 queue<pair<int, string> > que; 26 for (auto r : record[len - 1]) 27 que.push(pair<int, string>(len - r.length(), r)); 28 while (!que.empty()) { 29 pair<int, string> p = que.front(); 30 que.pop(); 31 if (p.first <= 0) 32 res.push_back(p.second); 33 else { 34 for (auto w : record[p.first - 1]) 35 que.push(pair<int, string>(p.first - w.length(), w + " " + p.second)); 36 } 37 } 38 39 return res; 40 }
原文：http://www.cnblogs.com/boring09/p/4235915.html