题目分析
之前我一直都在刷矩阵型，背包型的dp题目，今天我们来一道存在型的dp，这道题我觉得是比较有意思一点吧。（其实是相对简单一点，容易分析，困难题写不动，菜QAQ）
我相信很多小伙伴刷题都是为了应付面试，而应付面试，简单到中等的题目其实就够了，大部分公司都不会出很难的。再说了我只是个切图仔，困难题一般也hold不住啊，流下了没有技术的泪水。
题目分析
拿到题目我同样是先暴力解决，暴力解决我就不分析不写代码了，感兴趣的小伙伴们可以看我之前的文章，如果不考虑性能，回溯法是真香。
仔细观察题目，'leetcode' 返回 true 是因为可以被拆分为 ['leet','code'] 这两个单词，那最后一步是啥？就是 'code' 这个单词呀，再加上 'leet', 不就是答案了吗？这不是废话吗？这真不是废话，这是动态规划的题目套路，如果小伙伴们还达不到这种功力，你只需认真花费一段时间研究我之前写过的动态规划的文章，好好学习，我相信你动态规划绝对比我厉害很多；因为我真的很笨。
关于我为什么会这样思考题目，是因为我做了一段时间的dp题目了。有一定的经验，这种经验一旦你愿意花费点时间来积累，简单到中等的题目绝对是没有问题的，就看你能不能坚持下来了。
这种简单到中等的题目，我敢说90%都是直接根据示例答案去思考，思考最后一步，最优策略是什么，你想清楚了立马能写出答案。
- 定义状态
- 这里我再强调一遍，最有一步，最优策略是什么？最后一步就是code，上一步就是leet呀，那我们完全可以往问题的规模小的方向想，对应原字符串s，如果我们s='leet'，答案肯定很简单，但是再加一个'code'，我们该怎么办呢？假设a='leet', b='code'，那问题不就变成匹配这两个ab了，当a存在，且b也存在；答案不就出来了吗？
- 所以我们可以这样来定义状态，dp[j]表示，在原串上，由i到j的子串在不在字典中。
- 状态转移方程：dp[j] = map.has(s.substring(i, j)) and dp[i]
- map.has(s.substring(i, j)) i到j在不在字典中，dp[i] 表示前面一段也在字典中
- 边界和初始条件
- 初始值，也就是base case，初始值有些特殊，因为当我们判断 a 和 b 两段都在的情况下，此时是完全匹配上了，但是我们需要一个值来递推，怎么办呢？那就让子串为空的时候为真，方便我们递推，所以dp[0] = true
- 边界，需要用到一个空串，所有就是length + 1
代码
var wordBreak = function(s, wordDict) {
let n = s.length;
let dict = new Set(wordDict);
let dp = Array(n+1).fill(false);
dp[0] = true
for(let j = 1; j < n + 1; j++){
for(let i = 0; i < j; i++){
if(dict.has(s.substring(i, j)) && dp[i]){
dp[j] = true;
break;
}
}
}
return dp[n]
};
总结
面试题很多题目都是简单或者中等的dp题目，而这类的题目并不难，你只需要判断一下能不能用dp来做，同时直接根据示例答案思考，往问题规模小的方向来思考，由局部最优递推全局最优来定义状态，思考转移方程；往往这类题目的转移方程真的不难，只需要你入门就能很轻松的解决了。
