Leetcode中的完美广场

Question

我无法理解其中一个Leetcode问题.

给定一个正整数n,找到完全平方数的数量最少(例如,1,4,9,16,...),其总和为n.

例如,给定n = 12,返回3,因为12 = 4 + 4 + 4; 给定n = 13,返回2,因为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

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

让我们仔细看一下计算包含在数字中的最小正方形量的递推关系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);
}

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

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

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

在这种情况下,我们必须f(N)只记住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 2

我也很难过。让我们以数字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）中最小的一个。因此分钟。