package com.fishercoder.solutions;

/**
 * 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, num = 2;
        while (num * num <= n) {
            int temp1 = n / (num * num), temp2 = n % (num * num);
            result = Math.min(result, temp1 + numSquares(temp2));
            num++;
        }
        return result;
    }

}

@@ -28,16 +28,35 @@
 utions;%0A
+import java.util.*;
 %0A/**%0A * 
@@ -601,10 +601,470 @@
 %0A    %7D%0A%0A
+    //DP solution%0A    public int numSquaresDP(int n) %7B%0A        int%5B%5D dp = new int%5Bn + 1%5D;%0A        Arrays.fill(dp, Integer.MAX_VALUE);%0A        dp%5B0%5D = 0;%0A        dp%5B1%5D = 1;%0A        for(int i = 1; i %3C= n; i++) %7B%0A            int min = Integer.MAX_VALUE;%0A            int j = 1;%0A            while(i -j*j %3E= 0) %7B%0A                min = Math.min(min, dp%5Bi - j*j%5D + 1);%0A                j++;%0A            %7D%0A            dp%5Bi%5D = min;%0A        %7D%0A        return dp%5Bn%5D;%0A    %7D%0A%0A
 %7D%0A

edit 279 (#14)