package com.interview.dynamic;

/**
 * https://leetcode.com/problems/perfect-squares/
 */
public class MinimumNumberOfPerfectSquares {
    public int numSquares(int n) {
        int count = (int)Math.ceil(Math.sqrt(n));

        int[] T = new int[n + 1];

        T[0] = 0;

        for (int i = 1; i < T.length; i++) {
            T[i] = Integer.MAX_VALUE;
            for (int j = 1; j <= count; j++) {
                if (i < j*j) {
                    break;
                }
                T[i] = Math.min(T[i], T[i - j*j] + 1);
            }
        }
        return T[n];
    }
}

@@ -29,10 +29,604 @@
 c;%0A%0A
-/*
+import java.util.*;%0A%0A/**%0A * Date 10/19/2016%0A * @author Tushar Roy%0A *%0A * Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.%0A * For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.%0A *%0A * Solution 1 - Using DP similar to coin change problem with infinite supply%0A * Solution 2 - Using a BFS. Put all perfect squares in queue. Then considering each as a node try adding%0A * another perfect square and see if we can get n. Keep doing this in BFS fashion till you hit the number.%0A 
 *%0A *
@@ -747,16 +747,23 @@
 mSquares
+UsingDP
 (int n) 
@@ -1180,11 +1180,1246 @@
 %5D;%0A    %7D
+%0A%0A    public int numSquaresUsingBFS(int n) %7B%0A        List%3CInteger%3E perfectSquares = new ArrayList%3C%3E();%0A        int i = 1;%0A        Queue%3CInteger%3E queue = new LinkedList%3C%3E();%0A        Set%3CInteger%3E visited = new HashSet%3C%3E();%0A        while (true) %7B%0A            int square = i * i;%0A            if (square == n) %7B%0A                return 1;%0A            %7D%0A            if (square %3E n) %7B%0A                break;%0A            %7D%0A            perfectSquares.add(square);%0A            queue.offer(square);%0A            visited.add(square);%0A            i++;%0A        %7D%0A        int distance = 1;%0A        while (!queue.isEmpty()) %7B%0A            int size = queue.size();%0A            distance++;%0A            for (int j = 0; j %3C size; j++) %7B%0A                int node = queue.poll();%0A                for (int square : perfectSquares) %7B%0A                    int sum = node + square;%0A                    if (sum == n) %7B%0A                        return distance;%0A                    %7D else if (!visited.contains(sum)) %7B%0A                        visited.add(sum);%0A                        queue.add(sum);%0A                    %7D else if (sum %3E n) %7B%0A                        break;%0A                    %7D%0A                %7D%0A            %7D%0A        %7D%0A        return distance;%0A    %7D
 %0A%7D%0A

Add BFS method for perfect square qs