第33天。

做了超级久。。。还是没做出来，我真是菜啊，明明已经想到了要用动态规划来做了。

今天的题目是:Word Break:

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given s = “leetcode”, dict = [“leet”, “code”].

Return true because “leetcode” can be segmented as “leet code”.

因为没做出来，所以只能讲别人的思路了。。。

首先这里是要用动态规划去做的，我们需要一个vector<bool> db来记录s.substr(0,i+1)的子串是否能用wordDict进行break,如果我们要求db[i]我们是否能利用db[0:i]的值呢，比如，如果0<= k < i，且db[k]==true,那么我们是不是只需要在wordDict中查找是否有s.substr(i,k-i)就可了呢：

1
    bool wordBreak(string s,vector<string> &wordDict) {
2
        if(wordDict.size() == 0) return false;
3
        vector<bool> dp(s.size() + 1,false);
4
        dp[0] = true;
5
        for(int i = 1;i <= s.size();i++) {
6
            for(int j = i-1;j >= 0;j--) {
7
                if (dp[j]) {
8
                    string word = s.substr(j,i-j);
9
                    if (find(wordDict.begin(),wordDict.end(),word) != wordDict.end()) {
10
                        dp[i] = true;
11
                        break;
12
                    }
13
                }
14
            }
15
        }
2 collapsed lines
16
        return dp[s.size()];
17
    }

因为是别人的思路，所以也没法复现思考的过程了，总结一下没做出来的原因吧。 虽然说算法课上刚讲了DP,当时他讲的时候我还觉得挺简单的，还以为自己已经会了，因为之前已经做过好几次DP的题目了，现在想想上课我就记得他吐槽了DP的恋爱观，什么总是找局部最优解巴拉巴拉的。 哎，这种东西还是要自己体会才行，恩，决定了，这几天刷会DP的题目先。