Lint-Code完美平方

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

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

代码我是抄的别人的，但是要写博客还是要先看懂才行，这是用的迭代的方法，从一开一步一步逐渐迭代最终算到最后的字。可以这么理解：（我们用到的最小的平方数就是1）

1需要1个平方数，2在1的前提下+1且需要2个平方数，也就是无论你需所求得数有多大，一步一步迭代而来。

代码如下：

public static int numSquares(int n) {
      int[] dp=new int[n+1];  
         
        for(int i=0;i<=n;i++)  
            dp[i]=i;  
        for(int i=1;i<=n;i++)  
        {  
           int a=(int) Math.sqrt(i);  
           if(a*a==i)  
           {  
               dp[i]=1;  
           }  
           else  
           {  
               for(int j=1;j*j<=i;j++)  
               {  
                   dp[i]=Math.min(dp[i], dp[i-j*j]+1);  
               }  
           }  
        }  
          
       return dp[n];   
    }  
 public static void main(String[] args) {
  int num = numSquares(8);
  System.out.println(num);
 }
}