题目：
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"
思路：
之前想到的是使用循环一个一个试，对每个dict中 的元素进行s.contains的判断。然后再做处理。
但是，毫无疑问的超时了。原因就在于，做了太多的重复性工作。
如果验证样例中输入：baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa，[a],[a,a],[a,a,a],[a,a,a,a],[a,a,a,a,a],[a,a,a,a,a,a,a]
那么程序必然超时。
于是自然想到了动态规划（Dynamic Program），寻找转移方程：其实对于字符串abc，可以看成是ab+c，那么如果ab在dict中出现了，而c也出现了，或者abc整体出现了，
那么abc自然成立。而向前推：考虑ab。如果a出现了而b也出现了，或者ab整体出现了，那么ab也成立。再往前推到a，直接判断a是否出现。则转移方程就已经出来了：
使用w[]为状态标记，初始都是false。
w[i]表示，以下标i为结尾的s.substring(0,i)是否出现。
那么，从idx=0开始向后遍历以每一个字符结尾的w：
逻辑为这样：
如果idx=0，那么直接判断s.substring(0,i)是否出现，并赋值给w。
如果idx>0,则判断dict.contains(s.substring(0,idx+1)) || w[idx-1]&&dict.contains(s.substring(idx,idx+1)) || w[idx-2]&&dict.contains(s.substring(idx-1,idx+1)) || ...
直到全都遍历一遍或者在某个w状态下为true。
至此，w[idx]也出来了。以此类推。
AC代码：
public boolean wordBreak(String s, Set<String> dict) {
boolean[] w = new boolean[s.length()+1];
w[0]=true;
int size = s.length();
for(int i=0;i<size;i++){
if(dict.contains(s.substring(0,i+1))){
w[i+1] = true;
}
else{
if(i==0){
w[i+1] = dict.contains(s.substring(i,i+1));
}
else{
for(int j=i;j>=0;j--){
if(w[j] && dict.contains(s.substring(j,i+1))){
w[i+1] = true;
break;
}
}
}
}
}
return w[size];
}