]# Word Break
题目描述
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
解题方法
递归
首先能够想到的是，这是可以分解成子问题的，比如"leetcode", 前面已经可以break 成"leet"，那我们就只需要考虑后面"code"是否能够分解成word就可以了。
最直白的想法是recursion的call sub-problem.
DP
recursion的时间复杂度很高，根据recursion我们可以想到用dp做，cache之前的结果。
state
dp[i]表示s的前i个字符是否能够拆分
transition funciton
dp[i] = True if for any word of length k, dp[i-k] = True
init status
现在word的长度的地方是true
result
dp[n]