0279. Perfect Squares

https://leetcode.com/problems/perfect-squares

Description

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

**Input:** n = 12
**Output:** 3
**Explanation:** 12 = 4 + 4 + 4.

Example 2:

**Input:** n = 13
**Output:** 2
**Explanation:** 13 = 4 + 9.

Constraints:

• 1 <= n <= 104

ac1: DP

https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics)

class Solution {
    public int numSquares(int n) {
        // edge cases
        if (n < 4) return n;

        // init
        int[] dp = new int[n+1];
        dp[0] = 0; dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int min = Integer.MAX_VALUE;;
            for (int k = 1; i - k*k >= 0; k++) {
                min = Math.min(min, dp[i-k*k] + 1);
            }
            dp[i] = min;
        }

        return dp[n];
    }
}

// state: f[i], least number ... 
// function: f[i] = max(f[i-1^2], f[i-2^2]) + 1, while i - k^2 > 0;

ac2: BFS

time limit exceed layer -> need to have int size = q.size();

class Solution {
    public int numSquares(int n) {
        // edge cases
        if (n < 4) return n;

        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(n);

        int layer = 0;
        while (!q.isEmpty()) {
            layer++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int curr = q.poll();
                for (int k = 1; k*k <= curr; k++) {
                    if (curr - k*k == 0) return layer; 
                    q.offer(curr - k*k);
                }
            }
        }
        return layer;
    }
}

https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics)/73744