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.

BFS

public class Solution {
    public int numSquares(int n) {
        if (n < 2) return n;
        
        List<Integer> edges = new ArrayList<>();
        for (int i = 1; i * i <= n; i++) {
            edges.add(i*i);
        }
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(n);
        int level = 0;
        while (!queue.isEmpty()) {
            level++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int top = queue.poll();
                System.out.println(top);
                //neighbors
                for (int edge : edges) {
                    if (top == edge) {
                        return level;
                    } else if (top < edge) {
                        break;
                    } else {
                        queue.offer(top - edge);
                    }
                }
            }
        }
        return level;
    }
}

dp

//接龙型dp
public class Solution {
    public int numSquares(int n) {
        int[] record = new int[n+1];
        for (int i = 0; i <= n; i++) {
            record[i] = i;
            for (int j = 1; j * j <= i; j++) {
                record[i] = Math.min(record[i], record[i - j * j] + 1);
            }
        }
        return record[n];
    }     
}