给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。

样例

给出 n = 12, 返回 3 因为 12 = 4 + 4 + 4。

给出 n = 13, 返回 2 因为 13 = 4 + 9。

高级版本的动态规划

简单的动态规划 一般都是从dp[n]到dp[n+1] 

这里是 dp[n]到dp[n+i* i]

而且i是0到一个不溢出的最大值。 这个思路比较难想到，是一个难点

另一个就是dp长度是n+1，i和j都是从0开始， 这个边界条件的处理让程序简单起来

 

这个看起来很优美简洁的程序有一个很大的问题。 但是lintcode 竟然过了。。。

就是输入值是最大值的时候，第八行直接报错。

可能这个题考察的不是这个。想兼容这种情况  可以dp[n]用一个变量来单独保存，就是程序里面判断起来可能low一点儿，大家有没有更好的方法呢？（假装有人会看）

 

 

 

public class Solution {    /*     * @param n: a positive integer     * @return: An integer     */    public int numSquares(int n) {        // write your code here        int[] dp = new int[n+1];        for(int i =0; i<=n; i++){            dp[i] = Integer.MAX_VALUE;//初始化数组        }        for(int i = 0;i*i <= n; i++){            dp[i*i] = 1;   //把最小的这种完全平方的存进去                 }                for(int i = 0; i <= n; i++){
     //这里从零开始 边界条件的处理让整个程序简介起来            for(int j = 0; i+j*j <= n; j++){
     //和正常dp不同的地方，不是从dp[n]到dp[n+1]的操作 而是每次都是从dp[n]到若干个dp的逼近                dp[i+j*j] = Math.min(dp[i]+1,dp[i+j*j]);            }        }        return dp[n];    }}