一题看 无记忆化dfs、记忆化dfs和dp直接的转化

本文主要是介绍一题看 无记忆化dfs、记忆化dfs和dp直接的转化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

无记忆化dfs：

class Solution {
public:bool res=false;bool wordBreak(string s, vector<string>& wordDict) {set<string> S;int n=s.size();for(auto ss:wordDict){S.insert(ss);}function<void(int)> dfs=[&](int t){if(res==true) return ;if(t==n){res=true;}else{for(int i=t;i<n;i++){if(S.find(s.substr(t,i-t+1))!=S.end()){dfs(i+1);}}}};dfs(0);return res;}
};

记忆化dfs：

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {set<string> S;int n=s.size();vector<bool> path(n,0);for(auto ss:wordDict){S.insert(ss);}function<bool(int)> dfs=[&](int t){if(t==n){return true;}if(path[t]==true) return true;else{for(int i=t;i<n;i++){if( S.find(s.substr(t,i-t+1))!=S.end() && dfs(i+1) ){path[i]=true;return true;}}}return false;};bool res=dfs(0);return res;}
};

dp:

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {set<string> S(wordDict.begin(),wordDict.end());int n=s.size();vector<bool> dp(n+1,false);dp[0]=true;for(int i=1;i<=n;i++){for(int j=i-1;j>=0;j--){if(dp[j] && S.find(s.substr(j,i-j)) != S.end() ){dp[i]=true;break;}}}return dp[n];}
};

dp[i]表示i之前的所有能不能重组

这篇关于一题看 无记忆化dfs、记忆化dfs和dp直接的转化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---