[LeetCode] 139、单词拆分

题目描述给一个字符串和一些单词问字符串能不能由这些单词构成。每个单词可以用多次也可以不用。示例输入:sleetcode,wordDict[leet,code]输出:true解释:返回true因为leetcode可以被拆分成leet code。解题思路刚开始是超级暴力的想法利用回溯法找全排列用wordDict去生成所有可能的字符串。期间如果出现了目标字符串s就返回true。这种方法基本毫无疑问会超时动态规划这里最重要的是要想明白如何确定“状态表示”即状态应该定义为“什么的状态”参考53、300题然后如何状态转移如何由已知子问题的最优解得到大问题的最优解。其实下面那个练习和第一种dp思路一致不需要看。注动态规划和记忆化搜索本质没区别《算法导论》中统称为“动态规划”。只是方向不一样在评论区动态规划是打表格法自底向上解决问题其特点是每一次遇到大问题的时候与这个大问题有关的所有小问题都得到了解决。记忆化搜索是自顶向下解决问题每一次遇到大问题的时候与这个大问题有关的小问题未必都得到了解决但是解决了一个我们就记录一下以防止以后再遇到同样问题的时候从头开始再计算一次。我想“自底向上”与“自顶向下”是它们最主要的区别1、“自顶向下”是人的视角我们面对问题的时候是直接解决问题遇到一个问题解决一个问题所以需要记忆就像我们工作中遇到问题要写个笔记或者博客记录下来一样。2、“自底向上”有些资料上说是开启了上帝视角我很认同这种说法。显然动态规划也是用空间换时间也得记录从最小的问题开始做直到解决了最终的大问题。用动态规划我个人觉得比较好的一点是解决问题的方向比较有规律因此状态压缩就成为了可能不像记忆化搜索那样解决的问题到处跑。有的资料例如《算法导论》对它们二者就不区分都叫动态规划。参考代码classSolution{public:boolwordBreak(string s,vectorstringwordDict){if(s.empty()){returnfalse;}unordered_setstringwordDictSet(wordDict.begin(),wordDict.end());vectorbooldp(s.size(),false);dp[0]wordDictSet.find(s.substr(0,1))!wordDictSet.end();// c非常恶心的地方不能直接find(char)for(inti1;is.size();i){// 别忘记dp[i]可以直接find到的情况if(wordDictSet.find(s.substr(0,i1))!wordDictSet.end()){dp[i]true;continue;}for(intj0;ji;j){if(dp[j]wordDictSet.find(s.substr(j1,i-j))!wordDictSet.end()){dp[i]true;break;}}}returndp[s.size()-1];}};