Leetcode 中的完美正方形

Question

我无法理解一个 Leetcode 问题。

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.

解决方案：

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

我真的不明白 min(squares,dp[m-i*i]+1) 是怎么回事。能解释一下吗？

谢谢。

Answer 1

澄清你的困惑在于问题本身。结构 dp 包含总计 dp.

索引位置的 最少平方数

例如，当 n=9 时，squares 会 return 3，但最不可能的是 1，这就是 dp[m- i*i] + 1 return.

Answer 2

您提到的解决方案是算法的自下而上版本。为了更好地理解算法，我建议查看解决方案的自上而下版本。

让我们仔细看看包含在数字N中的最小完全平方数计算的递归关系。对于给定的 N 和任何任意数 x （被认为是最短数字序列的成员，其完全平方和为 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)

现在，考虑到考虑的递归，我们可以构建自上而下的解决方案（我将在 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);
}

给定解决方案的运行时复杂度是指数级的。

但是，我们可以注意到 n 的可能值只有 [1..n] 个，curr 的值只有 [1..sqrt(n)] 个。这意味着，函数 solve 的参数的不同值只有 n * sqrt(n) 组合。因此，我们可以创建记忆 table 并降低自上而下解决方案的复杂性：

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

给定的解决方案具有运行时复杂度 O(N * sqrt(N))。

但是，可以将运行时复杂度降低到 O(N)。

至于 f(N, x) 的递归关系仅取决于 f(N, x + 1) 和 f(N - x^2, 1) - 这意味着该关系可以等效地转换为循环形式：

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

在这种情况下，我们必须仅针对其参数的 N 个不同值来记忆 f(N)。因此，下面给出了 O(N) 自上而下的解决方案：

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;
}

最后，可以很容易地将提出的自上而下的解决方案转换为自下而上的解决方案：

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

Answer 3

我也很难过。让我们以数字 n=13 为例。

首先要观察的是：1^2 =1, 2^2=4, 3^2=9, 4^2=16
- 所以 13 不能由任何大于 3^2。一般来说，n只能由数字1到sqrt(n)
- 所以我们剩下以下数字的平方的某种组合：1、2 或 3。
接下来我们要做的是提出递归公式。这花了我很长时间才明白。但是我们基本上想要缩小以使用更小的 n （这就是递归的全部意义）。我们通过从 n 中减去我们的候选完美平方来做到这一点。例如：
- 如果我们尝试3，则dp(13)=dp(13-3^2)+1=dp(4)+1。 +1 将计数递增 1，这是因为我们已经从 13 中取出一个完美的正方形，即 3^2。每一个+1都是我们起飞的完美正方形。
- 如果我们尝试2，那么dp(13)=13-2^2=dp(9)+1
- 如果我们尝试1，那么dp(13)=13-1^2=dp(12)+1

所以我们剩下的就是比较 dp(4)、dp(9) 和 dp(12) 中哪个最小。因此最小

Leetcode 中的完美正方形

Perfect Square in Leetcode

c++

math

dynamic-programming

perfect-square