拆分词句II【C++】【动态规划】【回溯】

由于dict中可能存在多个前缀相同的单词，也就使得s可能有多种拆分方案，比如例题中的“nowcoderis”可以被拆分为"now coder is"和“now coderis"。如何才能计算出所有方案？

很直观的想法就是记录下每个分割点的位置，最后利用这些分割点的信息还原成一个语句即可。例如，“nowcoderis”有两个分割点，一个是分割点是'i'，另外一个是'c'，这两个分割点的索引分别为8，3，记录下这两个分割点，然后自底向上还原。（为什么是自底向上？因为在记录分割点的时候是自上而下的，每个位置记录的都是它之前的分割点，所以只能自底向上才能还原完整的索引信息）
具体的，创建一个二维数组dp，数组dp[i][j]表示如果s[0,i-1]可以被分割，分割的位置，这个位置可能有多个，也可能没有。然后利用dp数组中记录的信息计算最终结果，这个过程是自底向上的。

上面解释可能比较难懂，对例题来说，首先计算得到dp数组（省略了空行）：
dp[0] = {0}（这种情况对应字符串为空）
dp[3] = {0}（"now"可以拆分一个"now"出来）
dp[8] = {0}（"nowcoder"可以拆分一个"nowcoder"出来）
dp[10] = {3, 8} （s[3] == 'c', s[8] == 'i'，“nowcoderis”可以拆分一个"is"出来，或者拆分一个"coderis"）
dp[14] = {10} （s[10] == 'b'，"nowcoderisbest"可以拆分一个"best"出来）
然后从dp[14]开始（自底向上）还原语句，可以得到两条完整拆分信息，14->10->3->0，14->10->8->0，这个过程向上回溯即可。

时间复杂度O(n^2)

    vector<string> res;
    string path;
    void dfs(string& s, vector<vector<int>>& dp, int i) {
        if(i == 0) {
            path.pop_back();    //去掉末尾的空格
            res.push_back(path);
            return;
        }
        for(int j=0; j<dp[i].size(); ++j) {
            string temp = path;
            path = s.substr(dp[i][j], i-dp[i][j]) + " " + path;    //由于是自底向上还原，这里的顺序需要调整
            dfs(s, dp, dp[i][j]);
            path = temp;
        }
    }
    vector<string> wordBreak(string s, unordered_set<string> &dict) {
        int len = s.size();
        vector<vector<int>> dp(len+1);
        dp[0].push_back(0);
        for(int i=1; i<=len; ++i) {
            for(int j=0; j<i; ++j) {
                //dp[j].size()>0表示s[0,j-1]可以被拆分，dict.count(s.substr(j,i-j)表示dict中有s[j,i-1]这个单词
                //也就是说如果s[0,i-1]可以被拆分为s[0,j-1], s[j,i-1]
                if(dp[j].size()>0 && dict.count(s.substr(j,i-j))) {
                    dp[i].push_back(j);
                }
            }
        }
        dfs(s, dp, len);
        return res;
    }