单词分割

用两种方法来做（还有第三种方法，以后再看吧0.0）：

1. 动态规划（简单，适合本题）
2. 递归（有人把这叫DFS，我还纳闷了老半天，严格来说本题还有第三种方法BFS）

动态规划的话，理解比较清晰，写起来也比较简单。

递归的话，如果没有优化，会完全通过不了；优化过后，可以和DP媲美。

下面放出DP、DFS（有优化），DFS（无优化）的代码，供大佬们参考。

动态规划

//
// Created by jt on 2020/8/8.
//
#include 
using namespace std;
class Solution {
public:
    bool wordBreak(string s, unordered_set &dict) {
        // 动态规划：1\. 每一个状态和前一个状态有关；2\. 最小子状态是可以求得的
        // 转移方程：f(i)表示s[0,i]可以分词，那么f(i) = f(j) && f(j+1, i); (0<=j<i)
        int len = s.length();
        vector dp(len+1, false);
        dp[0] = true;
        for (int i = 1; i <= len; ++i) {        // 注意终止条件，此处从1开始，终止条件应该为len
            for (int j = i-1; j >= 0; --j) {
                if (dp[j] && dict.find(s.substr(j, i-j)) != dict.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[len];
    }
};

DFS（优化后）

//
// Created by jt on 2020/8/8.
//
#include 
using namespace std;
class Solution {
public:
    bool wordBreak(string s, unordered_set  &dict) {
        vector status(s.size(), -1);  // 这里不用布尔类型，因为需要存储三个状态（未访问、true和false）
        return dfs(s, dict, status, 0);
    }
    bool dfs(string &s, unordered_set  &dict, vector &status, int start) {
        if (start > s.size() - 1) return true;
        if (status[start] != -1) return status[start];
        for (int end = start + 1; end <= s.size(); ++end) {
            if (dict.find(s.substr(start, end - start)) != dict.end()
            && dfs(s, dict, status, end)) {
                status[start] = 1;
                return true;
            }
        }
        status[start] = 0;
        return false;
    }
};

DFS（无优化）

注释掉的部分好像能通过40%样例，但是是写错了的，哇哈哈。。。💩碰运气

//
// Created by jt on 2020/8/8.
//
#include 
using namespace std;
class Solution {
public:
    bool wordBreak(string s, unordered_set  &dict) {
        // 递归求解：(true)&&(true&&(true&&(true)))
        // 也可以理解为深度优先(DFS)
        int len = s.length();
        if (len == 0) return true;
        for (int i = 1; i <= len; ++i) {
            // 下面方法只能通过40%样例，注意用例："aaaaaaa",["aaaa","aaa"]
            // if (dict.find(s.substr(0, i)) != dict.end()) {
            //     return wordBreak(s.substr(i), dict);
            // }
            // 这个递归是正确的，但是由于效率过低，一个样例都过不了，呜呜
            if (dict.find(s.substr(0, i)) != dict.end() && wordBreak(s.substr(i), dict)){
                return true;
            }
        }
        return false;
    }
};