Perfect Square in Leetcode

问题:

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.

回答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];
}

回答2:

I had a hard time with this too. Let's take the example number n=13.

• First thing to observe is that: 1^2 =1, 2^2=4, 3^2=9, 4^2=16
  • So 13 can't be composed of anything greater than 3^2. Generically speaking, n can only be composed of numbers 1 to sqrt(n)
  • So we are left with some combination of the square of the following numbers: 1, 2, or 3.
• Next thing we want to do is come up with the recursive formula. This took me a long time to understand. But we basically want to dwindle down to work with a smaller n (that's the whole point of recursion). We do that by subtracting our candidate perfect squares from n. For example:
  • If we try 3, then dp(13)=dp(13-3^2)+1=dp(4)+1. The +1 is incrementing the count by 1 and is from the the fact that we already took off a perfect square from 13, which was the 3^2. Each +1 is a perfect square that we took off.
  • If we try 2, then dp(13)=13-2^2=dp(9)+1
  • If we try 1, then dp(13)=13-1^2=dp(12)+1

So we are left with comparing which is the smallest out of dp(4), dp(9), and dp(12). Hence the min.

回答3:

The clarification to your confusion lies in the question itself. The structure dp holds the least number of squares that sum up to the index position of dp.

E.g., squares would return 3 when n=9, but least possible is 1, which is what dp[m- i*i] + 1 would return.