c++ - 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

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