Leetcode 279 Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Solution 1: Use DP, O(n^3/2) solution

 public class Solution {  
   public int numSquares(int n) {  
     if (n<=0) return 0;  
     int[] dp=new int[n+1];  
     Arrays.fill(dp,Integer.MAX_VALUE);  
     for (int i=0; i<=n; i++) {  
       if (i==0) dp[i]=0;  
       else {  
         for (int j=1; j*j<=i; j++) {  
           dp[i]=Math.min(dp[i],1+dp[i-j*j]);  
         }  
       }  
     }  
     return dp[n];  
   }  
 }