从暴力递归-＞记忆化搜索-＞动态规划

leetcode139.单词拆分：

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true
因为 “leetcode” 可以被拆分成 “leet code”。

示例 2：

输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回
true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
注意你可以重复使用字典中的单词。

示例 3：

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解析：

显然可以通过递归每次列举出所有符合情况判断，同时由于列举的过程中，后续子序列出现重复问题，因此通过记忆化搜索减少搜索量，同样可以通过递归函数改造为动态规划问题。

代码：

递归

 class Solution {
public:
    bool dfs(string s, int index,unordered_map<string,int> &smap,vector<string>& wordDict){
    	//到了最后，返回true
        if(index==s.size())
            return true;
        for(int i=1;i<s.size()-index+1;i++){
            if(smap[s.substr(index,i)]!=0&&dfs(s,index+i,smap,wordDict))
                return true;
        }
        //for中没有返回true说明都不符合，直接返回false
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_map<string,int> smap;
        for(int i=0;i<wordDict.size();i++){
            smap[wordDict[i]]=1;
        }
        return dfs(s,0,smap,wordDict);
    }
};

//记忆化搜索，遵循有则返回，无则先存后返回
class Solution {
public:
    bool dfs(string s, int index,vector<int> &dp,unordered_map<string,int> &smap,vector<string>& wordDict){
        if(index==s.size())
            return true;
        if(dp[index]!=-1)
            return dp[index];
        for(int i=1;i<s.size()-index+1;i++){
        	//截取到当前位置的单词存在，查看后续单词是否存在
            if(smap[s.substr(index,i)]!=0
            &&dfs(s,index+i,dp,smap,wordDict)){
                    dp[index]=1;
                return dp[index];
            }
        }
        dp[index]=0;
        return dp[index];
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_map<string,int> smap;
        vector<int> dp(s.size(),-1);
        for(int i=0;i<wordDict.size();i++){
            smap[wordDict[i]]=1;
        }
        return dfs(s,0,dp,smap,wordDict);
    }
};

//动态规划
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_map<string,int> smap;
        vector<int> dp(s.size()+1,0);
        for(int i=0;i<wordDict.size();i++){
            smap[wordDict[i]]=1;
        }
        dp[s.size()]=1;
        //dp数组赋值,从后往前推，前边依赖后边（看递归过程）
        for(int i=s.size()-1;i>=0;i--){
            for(int j=1;j<=s.size()-i;j++){
                if(smap[s.substr(i,j)]!=0&&dp[i+j]!=0)
                        dp[i]=1;
                }      
            }
        return dp[0];
    }
};