package com.fishercoder.solutions;

import java.util.Arrays;

/**
 * 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.
 */
public class _279 {

    public int numSquares(int n) {
        int result = n;
        int num = 2;
        while (num * num <= n) {
            int temp1 = n / (num * num);
            int temp2 = n % (num * num);
            result = Math.min(result, temp1 + numSquares(temp2));
            num++;
        }
        return result;
    }

    //DP solution
    public int numSquaresDP(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            int j = 1;
            while (i - j * j >= 0) {
                min = Math.min(min, dp[i - j * j] + 1);
                j++;
            }
            dp[i] = min;
        }
        return dp[n];
    }

}

@@ -59,16 +59,43 @@
 s;%0A%0A/**%0A
+ * 279. Perfect Squares%0A *%0A
  * Given
@@ -213,17 +213,18 @@
 m to n.%0A
-%0A
+ *
  For exa
@@ -343,17 +343,56 @@
  _279 %7B%0A
-%0A
+    public static class Solution1 %7B%0A    
     publ
@@ -422,24 +422,28 @@
 ) %7B%0A        
+   
+ 
 int result =
@@ -450,24 +450,28 @@
  n;%0A        
+    
 int num = 2;
@@ -475,24 +475,28 @@
  2;%0A        
+  
+  
 while (num *
@@ -504,24 +504,28 @@
 num %3C= n) %7B%0A
+    
             
@@ -557,32 +557,36 @@
 m);%0A            
+ 
+   
 int temp2 = n %25 
@@ -590,32 +590,36 @@
  %25 (num * num);%0A
+    
             resu
@@ -680,16 +680,20 @@
         
+    
 num++;%0A 
@@ -691,34 +691,42 @@
  num++;%0A        
+   
+ 
 %7D%0A
+    
         return r
@@ -736,19 +736,69 @@
 lt;%0A    
-%7D%0A%0A
+    %7D%0A    %7D%0A%0A    public static class Solution2 %7B%0A    
     //DP
@@ -807,24 +807,28 @@
 olution%0A    
+  
+  
 public int n
@@ -836,18 +836,16 @@
 mSquares
-DP
 (int n) 
@@ -854,16 +854,20 @@
         
+   
+ 
 int%5B%5D dp
@@ -885,16 +885,20 @@
 n + 1%5D;%0A
+    
         
@@ -941,16 +941,20 @@
         
+  
+  
 dp%5B0%5D = 
@@ -956,16 +956,20 @@
 0%5D = 0;%0A
+    
         
@@ -987,16 +987,20 @@
         
+ 
+   
 for (int
@@ -1018,24 +1018,28 @@
 = n; i++) %7B%0A
+    
             
@@ -1075,24 +1075,28 @@
             
+    
 int j = 1;%0A 
@@ -1102,24 +1102,28 @@
             
+   
+ 
 while (i - j
@@ -1131,24 +1131,28 @@
 * j %3E= 0) %7B%0A
+    
             
@@ -1211,16 +1211,20 @@
         
+  
+  
 j++;%0A   
@@ -1224,32 +1224,36 @@
 ++;%0A            
+    
 %7D%0A            dp
@@ -1250,16 +1250,20 @@
         
+ 
+   
 dp%5Bi%5D = 
@@ -1267,16 +1267,20 @@
  = min;%0A
+    
         
@@ -1285,24 +1285,28 @@
   %7D%0A        
+    
 return dp%5Bn%5D
@@ -1307,16 +1307,26 @@
  dp%5Bn%5D;%0A
+        %7D%0A
     %7D%0A%0A%7D

refactor 279