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的难点之一就是什么时候使用它。 当看到这个问题的时候，其实一开始是不知道要用哪种技巧来解这个问题的。 那么我们为什么可以用DP来解这道题呢？
因为，这个问题可以被更小的子问题解决。 比如说n现在=100， 找哪几个square number组成100. 那要是我们提前知道了square number 99的答案，那100不是分分钟解决。
所以做DP问题的时候，一个小技巧就是问自己，这个题目假设我已经知道了subproblem的答案，能不能分分钟解了这个题。可以的话，我们把每个小问题都建立在小小问题的答案的基础上解出来，这样iteratively，可以解决最后的这个大问题。
所以具体怎么做呢？ 要先看看pattern：
dp[0]怎么解？ 当然是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就好， 只要最终的结果dp[amount] 有解就好说。
然后做了这些DP题，发现真的要格外小心dp[x-0]的情况，因为dp[x]初始化是0，dp[x-0]=dp[x] 在取最小值中会被误以为这个就是最优解。
