279 Perfect Squares

279. Perfect Squares

1. Question

Given a positive integern, find the least number of perfect square numbers (for example,1, 4, 9, 16, ...) which sum ton.

For example, givenn=12, return3because12 = 4 + 4 + 4; givenn=13, return2because13 = 4 + 9.

2. Implementation

(1) BFS

class Solution {
    public int numSquares(int n) {
        int upperBound = (int)Math.sqrt(n);
        int[] squares = new int[upperBound];

        for (int i = 1; i <= upperBound; i++) {
            squares[i - 1] = i * i;
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);

        boolean[] visited = new boolean[n + 1];
        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            ++level;

            for (int i = 0; i < size; i++) {
                int curNum = queue.remove();
                visited[curNum] = true;

                for (int square : squares) {
                    int nextNum = curNum + square;

                    if (nextNum > n) {
                        break;
                    }
                    else if (nextNum == n) {
                        return level;
                    }
                    else if (!visited[nextNum]) {
                        queue.add(nextNum);
                    }
                }
            }
        }
        return level;
    }
}

(2) DP

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

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

(3) Memoization

public class Solution {
    public int numSquares(int n) {
        int[] cache = new int[n + 1];
        return dfs(n, cache);
    }

    public int dfs(int n, int[] cache) {
        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }

        if (cache[n] != 0) {
            return cache[n];
        }

        int num = Integer.MAX_VALUE;

        for (int i = 1; i * i <= n; i++) {
            num = Math.min(num, dfs(n - i * i, cache) + 1);
        }
        cache[n] = num;
        return num;
    }
}

3. Time & Space Complexity

BFS: 时间复杂度O(n * sqrt(n)), 空间复杂度O(n)

DP: 时间复杂度O(n * sqrt(n)), 空间复杂度O(n)

Memoization: 时间复杂度O(n * sqrt(n)), 空间复杂度O(n)