這道題做的很值。
題不難，但是考察點(diǎn)很明確。
做DP的最大問(wèn)題就是用遞歸，忘記用table來(lái)寫(xiě)。然后不停重復(fù)計(jì)算，exponential的運(yùn)算增長(zhǎng)，直接就爆了。這道題之所以是medium估計(jì)也是考這個(gè)的。

這個(gè)是典型的時(shí)間會(huì)爆掉的代碼：

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if(s == null || s.length() == 0)    throw new IllegalArgumentException("Invalid Input");
        int len = s.length();
        for(int i=1; i<=s.length(); i++) {
            String str = s.substring(0,i);
            if(wordDict.contains(str) && (i==len || wordBreak(s.substring(i,len), wordDict)))
                return true;
        }
        return false;
    }
}

用DP做的代碼：
沒(méi)什么好說(shuō)的。

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        boolean[] mem = new boolean[s.length() + 1];
        mem[0] = true;
        for (int i=1; i<=s.length(); i++) {
            for (int j=0; j<i; j++) {
                if (mem[j] && wordDict.contains(s.substring(j,i))) {
                    mem[i] = true;
                    break;
                }
            }
        }
        return mem[s.length()];
    }
}

重復(fù)計(jì)算是DP里面用遞歸的大忌，這種一般要用top-down，memory做table。
不能重復(fù)計(jì)算，不能重復(fù)計(jì)算，不能重復(fù)計(jì)算！重要的事情說(shuō)三遍！
============
much more effective at night.
How to block the sunshine during the day?
I will try to coding in my closet tomorrow : )