2

我无法理解 Leetcode 问题之一。

给定一个正整数 n，找出总和为 n 的最小完美平方数（例如，1、4、9、16，...）。

例如，给定 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)。你能解释一下吗？

谢谢。

4

3 回答 3

11

我也遇到了困难。让我们以数字 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) 中哪个最小。因此分钟。

于 2017-02-15T19:14:56.417 回答
8

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

让我们仔细看看计算包含在 number 中的最少量的完美平方的递归关系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)]currn * sqrt(n)solve

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];
}
于 2016-08-20T12:29:30.193 回答
0

澄清你的困惑在于问题本身。该结构dp包含最少数量的平方和 的索引位置dp。

例如，squares会3在 时返回n=9，但最不可能的是1，这是dp[m- i*i] + 1会返回的。

于 2016-08-19T04:45:20.090 回答