Perfect Square in Leetcode

Question

I am having trouble understanding one of a Leetcode Problem.

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.

Solution:

int numSquares(int n) {
    static vector<int> dp {0};
    while (dp.size() <= n) {
        int m = dp.size(), squares = INT_MAX;
        for (int i=1; i*i<=m; ++i)
            squares = min(squares, dp[m-i*i] + 1);
        dp.push_back(squares);
    }
    return dp[n];
}

I really dont understand what is going on with min(squares,dp[m-i*i]+1). Can you please explain?

thx.

Answer 1

The solution, which you have mentioned, is the bottom-up version of the algorithm. In order to understand the algorithm better, I would advice to look at the top-down version of the solution.

Let's look closer at the recurrence relation for the calculation of the minimal amount of the perfect squares, contained inside the number N. For given N and any arbitrary number x (which is the candidate for being considered as the member of the shortest sequence of numbers, whose perfect squares sums-up to N):

f(N, x) = 0                                 , if N = 0    ;
f(N, x) = min( f(N, x + 1), f(N - x^2, 1) ) , if N >= x^2 ;
f(N, x) = +infinity                         , otherwise   ;

solution(N) = f(N, 1)

Now, having in mind the considered recurrence, we can construct the top-down solution (I will implement it in Java):

int solve(int n) {
    return solve(n, 1);
}

int solve(int n, int curr) {
    if (n == 0) {
        return 0;
    }
    if ((curr * curr) > n) {
        return POSITIVE_INFINITY;
    }
    // if curr belongs to the shortest sequence of numbers, whose perfect squares sums-up to N
    int inclusive = solve(n - (curr * curr), 1) + 1;
    // otherwise:
    int exclusive = solve(n, curr + 1);
    return Math.min(exclusive, inclusive);
}

The runtime complexity of the given solution is exponential.

However, we can notice that there are only [1..n] possible values of n and [1..sqrt(n)] values of curr. Which, implies, that there are only n * sqrt(n) combinations of different values of arguments of the function solve. Hence, we can create the memoization table and reduce the complexity of the top-down solution:

int solve(int n) {
    // initialization of the memoization table
    int[][] memoized = new int[n + 1][(int) (Math.sqrt(n) + 1)];
    for (int[] row : memoized) {
        Arrays.fill(row, NOT_INITIALIZED);
    }
    return solve(n, 1, memoized);
}

int solve(int n, int curr, int[][] memoized) {
    if (n == 0) {
        return 0;
    }
    if ((curr * curr) > n) {
        return POSITIVE_INFINITY;
    }
    if (memoized[n][curr] != NOT_INITIALIZED) {
        // the sub-problem has been already solved
        return memoized[n][curr];
    }

    int exclusive = solve(n, curr + 1, memoized);
    int inclusive = solve(n - (curr * curr), 1, memoized) + 1;
    memoized[n][curr] = Math.min(exclusive, inclusive);

    return memoized[n][curr];
}

Given solution has the runtime complexity O(N * sqrt(N)).

However, it is possible to reduce the runtime complexity to O(N).

As far as the recurrence relation for f(N, x) depends only on f(N, x + 1) and f(N - x^2, 1) - it means, that the relation can be equivalently transformed to the loop form:

f(0) = 0
f(N) = min( f(N - x^2) + 1 ) , across the all x, such that x^2 <= N

In this case we have to memoize the f(N) only for N different values of its argument. Hence, below presented the O(N) top-down solution:

int solve_top_down_2(int n) {
    int[] memoized = new int[n + 1];
    Arrays.fill(memoized, NOT_INITIALIZED);
    return solve_top_down_2(n, memoized);
}

int solve_top_down_2(int n, int[] memoized) {
    if (n == 0) {
        return 0;
    }
    if (memoized[n] != NOT_INITIALIZED) {
        return memoized[n];
    }

    // if 1 belongs to the shortest sequence of numbers, whose perfect squares sums-up to N
    int result = solve_top_down_2(n - (1 * 1)) + 1;

    for (int curr = 2; (curr * curr) <= n; curr++) {
        // check, whether some other number belongs to the shortest sequence of numbers, whose perfect squares sums-up to N
        result = Math.min(result, solve_top_down_2(n - (curr * curr)) + 1);
    }

    memoized[n] = result;
    return result;
}

Finally, the presented top-down solution can be easily transformed to the bottom-up solution:

int solve_bottom_up(int n) {
    int[] memoized = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        memoized[i] = memoized[i - (1 * 1)] + 1;
        for (int curr = 2; (curr * curr) <= i; curr++) {
            memoized[i] = Math.min(memoized[i], memoized[i - (curr * curr)] + 1);
        }
    }
    return memoized[n];
}