题目描述：
给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。
说明：拆分时可以重复使用字典中的单词。
题目链接戳此
思路：首先将字典放进set里面，方便判断字典中是否包含某个单词，并求出字典中最长单词的长度（下面解析中有解释）。再根据题意，如果一个字符串合法（即拆分后的单词全都在字典里能查询到），那么这个字符串去掉一个单词也是合法的，由此能得到动态转移方程。
具体实现根据下面代码解析：如果在单词长度为 i 时，j 从 i - 1开始向前探索，一直探索到0位置时，如果满足 s的（i - j）不分的字符串存在于字符串，并且dp[0]为true，就说明这一段存在于字典里，这是定义dp[i] = true，假设此时的i位置为k。下一次探索的时候j从新的i-1位置开始，此时就不用探索到0位置才能返回true了，因为只要j从i位置开始走，到k的位置，满足[k,j]这一段存在字典中就可以了，if条件里dp[k]在上一次已经被置为true了，符合条件语句的判断。
刚才描述的代码还是可以优化的，也就是j 从 i - 1开始向前探索，一直探索到0位置，如果中间发现i-j大于字典中出现的单词中最大的长度，那么字典就不可能包含这个单词，所以可以在if语句多加上这个条件。这也就是剪枝思想。
代码实现如下：
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int len = s.length();
int max = 0;
Set<String> set = new HashSet<>();
for (String str : wordDict) {
if (!set.contains(str)) {
set.add(str);
max = Math.max(max,str.length());
}
}
boolean[] dp = new boolean[len + 1];
//dp[0]本身没有意义，题目中给的s是非空的，这里只是方便解题给定的初始值。
dp[0] = true;
for (int i = 1; i <= s.length();i++) {
//i - j <= max作用：剪枝。如果探索的长度大于字典里最长单词的长度，就没必要继续探索了。
for (int j = i - 1;j >= 0 && i - j <= max ;j--) {
if (dp[j] && set.contains(s.substring(j,i))) {
dp[i] = true;
break;
}
}
}
return dp[len];
}
}