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

Divide and conquer

For f(n) stands for the least number of perfect square numbers, then:

f(n) = min (f(n - 1^2) + 1, f(n - 2^2) + 1, f(n - 3^2) + 1, ..., f(n - k^2) + 1)

where n - k^2 >= 0, f(0) = 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public int numSquares(int n) {
        if (n == 0) {
            return 0;
        }
        int i = 1;
        int rst = Integer.MAX_VALUE;
        while ((n - i * i) >= 0) {
            rst = Math.min(rst, numSquares(n - i * i) + 1);
            i++;
        }
        return rst;
    }
}

The function grows factorial which could be improved by using dynamic programming.

DP

The intermediate result can be cached and later reused by future calls.

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 1; i - j * j >= 0; j++) {
                dp[i] = Math.min(dp[i - j * j] + 1, dp[i]);
            }
        }
        return dp[n];
    }
}