Perfecr Square 問題：
/*Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
其實吧抖单，我一直覺得DP的難點之一就是什么時候使用它。 當(dāng)看到這個問題的時候岂贩，其實一開始是不知道要用哪種技巧來解這個問題的战转。 那么我們?yōu)槭裁纯梢杂肈P來解這道題呢院水？
因為，這個問題可以被更小的子問題解決掘而。 比如說n現(xiàn)在=100谆趾， 找哪幾個square number組成100. 那要是我們提前知道了square number 99的答案，那100不是分分鐘解決嫁盲。
所以做DP問題的時候篓叶，一個小技巧就是問自己，這個題目假設(shè)我已經(jīng)知道了subproblem的答案羞秤，能不能分分鐘解了這個題缸托。可以的話瘾蛋，我們把每個小問題都建立在小小問題的答案的基礎(chǔ)上解出來俐镐，這樣iteratively，可以解決最后的這個大問題哺哼。
所以具體怎么做呢佩抹？ 要先看看pattern：
dp[0]怎么解？ 當(dāng)然是0啊
DP[1] 怎么解取董？ 一個1*1 就可以了對吧棍苹。DP[2]怎么用subprobelm解？ dp[1]+1對吧
dp[3]怎么解茵汰？ dp[2]+1就可以解了對吧枢里。dp[4]呢？ 都知道2*2=4蹂午，一個perfect square就可以了栏豺。那formula呢? dp[4] =dp[4-2*2]=subproblem dp[0]多一步達到。
知道了這些豆胸，我們就可以做題啦
Coin change問題跟Perfect squares簡直一模一樣
//subproblem : amount is 0, 1,2. large problem = amount is 10, dp[amount - coin denomion]+1;
唯一要注意的就是什么時候該返回-1 as result.
例如coins=[2], target amount = 1. 沒辦法達成冰悠，返回-1.
如果是coins=[2], target amount =4. 盡管subproblem DP[1] 也沒法達成，這里不需要返回-1, let dp[1]=-1就好配乱， 只要最終的結(jié)果dp[amount] 有解就好說。
然后做了這些DP題皮迟，發(fā)現(xiàn)真的要格外小心dp[x-0]的情況搬泥，因為dp[x]初始化是0，dp[x-0]=dp[x] 在取最小值中會被誤以為這個就是最優(yōu)解伏尼。
