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:

Bottom-up DP.

dp[n]=Math.min(dp[n-1]+1,dp[n-4]+1,dp[n-9]+1.....)

There is a very fast and decent Mathematics solution using

Legendre's three-square theorem

Please see the discussion tab in the Leetcode.

 public int numSquares(int n) {  
     int[] dp=new int[n+1];  
     for(int i=1;i<=n;i++){  
       int j=1;  
       dp[i]=i;  
       while(i>=j*j){  
         dp[i]=Math.min(dp[i],dp[i-j*j]+1);  
         j++;  
       }  
     }  
     return dp[n];  
   }