单词拆分
使用词典列表里的单词拼成字符串s，每个单词可以使用0次或无数次，能拼成返回true，反则false
分析
一个个单词拼接，所以字符串的最后必然是个单词，枚举长度（1 到 词典列表最长单词长度MAX_LEN），看看其substring是否是词典列表里的词，如果枚举到了词典列表最长单词长度也没有匹配的单词，或者是substring的字符串已经是完整字符串了也没有匹配的单词，说明一定是false。
如果substring是单词列表里的词，则问题转换为规模更小的子问题。
我们使用dfs(i)表示 能否用词典列表里的词拼成s.substring(0,i-1)所对应的字符串。
枚举最后一个单词的长度:
- 长度为1。s.substring(i-1,i)所得字符串是否在词典列表里，如果在，问题转换为dfs(i-1)，如果子问题是true，直接提前结束，返回true表示可以拼成。
- 长度为2。s.substring(i-2,i)所得字符串是否在词典列表里，如果在，问题转换为dfs(i-2)
- …
- s.substring( max(i-MAX_LEN,0) ， i）所得字符串是否在词典列表里，如果在，问题转换为dfs( max(i-MAX_LEN,0) )
- 枚举结束
递归入口：dfs(n)
递归边界条件：如果i-1<0 , 说明拼接成功，返回true。
class Solution {int MAX_LEN;int[] dp;public boolean wordBreak(String s, List<String> wordDict) {Map<String,Integer> dict=new HashMap<>();dp=new int[s.length()];for (int i=0;i<s.length();i++){dp[i]=-1;}for (String word:wordDict){dict.put(word,1);if (word.length()>MAX_LEN){MAX_LEN=word.length();}}return dfs(s.length(),s,dict)==1;}public int dfs(int i,String s,Map<String,Integer> dict){if (i-1<0){return 1;}String tmp;for (int j=1;j<=MAX_LEN&&i-j>=0;j++){tmp = s.substring(i-j,i);if (dict.containsKey(tmp)){if (dp[i-j]==-1){dp[i-j] = dfs(i-j,s,dict);}if (dp[i-j]==1){return 1;}}}return 0;}
}
1:1改成备忘录写法：
之前都是思考用前i个数（种物品），是否能够达到和（不超过质量），两个变量，一个是几个数（物品），一个是和（重量）
此题是思考能否把前0-i位置的字符串，分成多段，使得每段在词典列表里。一个变量，0-哪个位置。
dp[i]表示 能否把0到i-1位置的字符串分为多段，使得每段都在词典列表里。
初始值dp[0]=true
计算dp[i]，从后往前枚举长度为1,2,3…的字符串
- 长度为1. s.substring(i-1,i)所得字符串是否在词典列表里，如果在，并且dp[i-1]已经有值，可以得到当前拼法 是否可以拼成0到i位置的字符串
class Solution {public boolean wordBreak(String s, List<String> wordDict) {int max_len=0;String tmp;int[] dp=new int[s.length()+1];Map<String,Integer> dict=new HashMap<>();for (String word:wordDict){dict.put(word,1);if (word.length()>max_len){max_len=word.length();}}dp[0]=1;for (int i=1;i<=s.length();i++){for (int j=1;j<=max_len&&i-j>=0;j++){tmp = s.substring(i-j,i);if (dict.containsKey(tmp)){if (dp[i-j]==1){dp[i]=1;}}}}return dp[s.length()]==1;}
}