139. Word Break

##### dp

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> dict;
        for(auto& word : wordDict)
        {
            dict.insert(word);
        }
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for(size_t i = 1; i <= s.size(); ++i)
        {
            for(size_t j = 0; j < i; ++j)
            {
                if(dp[j] && (dict.find(s.substr(j, i - j)) != dict.end())) // 对于后面的i来说，要用到前面的结果，如果某一块前面部分是true的且剩下的也是可分的，那么这一块也是true，就不用重复判断前面部分了
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp.back();
    }
};
};

T(n) : O(n^2) ?
S(n) : O(n)

动态规划：用数组存储子问题的值，用子问题的值直接得到现在问题的值