dp[i]表示[0,...i-1]是否是合法字符串，因为dp[i]的状态不只是由dp[i-1]决定的，而是前边每个地方都有可能成为断点，只要有一个结果是true，则结果就是true,所以对于每个dp[i]遍历其之前的每个断点
class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set <string> wordDictSet ; for (auto word: wordDict) { wordDictSet.insert(word); } auto dp = vector <bool> (s.size() + 1); dp[0] = true; for (int i = 1; i <= s.size(); ++i) { for (int j = 0; j < i; ++j) { if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) { dp[i] = true; break; } } } return dp[s.size()]; } };