完全平方数

2021-01-16

279. 完全平方数

难度中等966

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

1
2
3

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

1
2
3

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

1 <= n <= 104

动态规划方法

将给定的数字看成背包的容量，将生成的完全平方数看成物品，转换成0-1背包问题，外层枚举背包的容量，内层枚举物品的重量

class Solution {
    public int numSquares(int n) {

        // 计算不大于n的完全平方数的个数
        int sqNum = (int) Math.sqrt(n) + 1;
        int[] sqArray = new int[sqNum];
        // 生成完全平方数
        for (int i = 1; i < sqNum; i++) {
            sqArray[i] = i * i;
        }
        int[] dp = new int[n + 1];
        // 初始化
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        // 0-1背包的动态规划，外层枚举背包的容量，内层枚举物品的重量
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < sqNum; j++) {
                if (i < sqArray[j]) break;
                dp[i] = Math.min(dp[i], dp[i - sqArray[j]] + 1);
            }
        }
        return dp[n];
    }
}

数学方法

四平方和定理，也称为 Bachet 猜想，它指出每个自然数都可以表示为四个整数平方和:

$p=a_{0}^{2}+a_{1}^{2}+a_{2}^{2}+a_{3}^{2}$

三平方定理完成了四平方定理，证明了正整数可以表示为三个平方和的一个特殊条件:

$n \neq 4^{k}(8 m+7) \Longleftrightarrow n=a_{0}^{2}+a_{1}^{2}+a_{2}^{2}$

其中 $k$ 和 $m$ 是整数。

首先，三平方定理告诉我们，如果 $n$ 的形式是 $n = 4^{k}(8m+7)$，那么 n 不能分解为 3 个平方的和。此外，我们还可以断言 $n$ 不能分解为两个平方和，数本身也不是完全平方数。因为假设数 $n$ 可以分解为 $n = a_{0}^{2}+a_{1}^{2}$，然后通过在表达式中添加平方数 $0$，即 $n = a_{0}^{2}+a_{1}^{2} + 0^2$，我们得到了数 $n$ 可以分解为 3 个平方的结论，这与三平方定理相矛盾。因此，结合四平方定理，我们可以断言，如果这个数不满足三平方定理的条件，它只能分解成四个平方和。

如果这个数满足三平方定理的条件，则可以分解成三个完全平方数。但我们不知道的是，如果这个数可以分解成更少的完全平方数，即一个或两个完全平方数。

所以在我们把这个数视为底部情况（三平方定理）之前，还有两种情况需要检查，即：

情况 1：如果数字本身是一个完全平方数，这很容易检查，例如 $n == int(sqrt(n)) ^ 2$。

情况 2：如果这个数可以分解成两个完全平方数和。不幸的是，没有任何数学定理可以帮助我们检查这个情况。我们需要使用枚举方法。

作者：LeetCode
链接：https://leetcode-cn.com/problems/perfect-squares/solution/wan-quan-ping-fang-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。


class Solution {

  protected boolean isSquare(int n) {
    int sq = (int) Math.sqrt(n);
    return n == sq * sq;
  }

  public int numSquares(int n) {
    // four-square and three-square theorems.
    while (n % 4 == 0)
      n /= 4;
    if (n % 8 == 7)
      return 4;

    if (this.isSquare(n))
      return 1;
    // enumeration to check if the number can be decomposed into sum of two squares.
    for (int i = 1; i * i <= n; ++i) {
      if (this.isSquare(n - i * i))
        return 2;
    }
    // bottom case of three-square theorem.
    return 3;
  }
}

作者：LeetCode
链接：https://leetcode-cn.com/problems/perfect-squares/solution/wan-quan-ping-fang-shu-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。