斐波那契数列中的完全平方数(LeetCode 题解 | 279. 完全平方数)

斐波那契数列中的完全平方数有144。这个问题涉及了两个概念。一个是斐波那契数列，一个是完全平方数。斐波那契数列是指从第三...更多斐波那契数列中的完全平方数的这个问题，以及大家所关心的LeetCode 题解 | 279. 完全平方数的内容，欢迎大家继续分享关注常识网。

斐波那契数列中的完全平方数

斐波那契数列中的完全平方数有144。这个问题涉及了两个概念。一个是斐波那契数列，一个是完全平方数。斐波那契数列是指从第三项起，每一项都是前面两项的和，而完全平方数是指这个数字是某个数字的平方。因此，从这两个概念上讲，我们找到了144。

斐波那契数列中的完全平方数拓展阅读

斐波那契数列中的完全平方数(LeetCode 题解 | 279. 完全平方数)

LeetCode 题解 | 279. 完全平方数

力扣 279. 完全平方数 （点击查看题目）

题目描述

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

示例 1 ：

输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4.

示例 2 ：

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

解决方案

方法一：暴力枚举法 [超出时间限制]

这个问题要求我们找出由完全平方数组合成给定数字的最小个数。我们将问题重新表述成：

给定一个完全平方数列表和正整数 n，求出完全平方数组合成 n 的组合，要求组合中的解拥有完全平方数的最小个数。

注：可以重复使用列表中的完全平方数。

从上面对这个问题的叙述来看，它似乎是一个组合问题，对于这个问题，一个直观的解决方案是使用暴力枚举法，我们枚举所有可能的组合，并找到完全平方数的个数最小的一个。

我们可以用下面的公式来表述这个问题：

从上面的公式中，我们可以将其转换为递归解决方案。这里有一个例子。

算法：

Python 实现

class Solution(object): def numSquares(self, n): square_nums = [i**2 for i in range(1, int(math.sqrt(n))+1)] def minNumSquares(k): &34;&34;&34; 39;inf& Find the minimal value among all possible solutions for square in square_nums: if k < square: break new_num = minNumSquares(k-square) + 1 min_num = min(min_num, new_num) return min_num return minNumSquares(n)

上面的解决方案可以适用于较小的正整数 n。然而，会发现对于中等大小的数字（例如 55），我们也会很快遇到超出时间限制的问题。

简单的说，可能会由于过度递归，产生堆栈溢出。

方法二：动态规划

使用暴力枚举法会超出时间限制的原因很简单，因为我们重复的计算了中间解。我们以前的公式仍然是有效的。我们只需要一个更好的方法实现这个公式。

你可能注意到从公式看来，这个问题和斐波那契数问题类似。和斐波那契数一样，我们由几种更有效的方法来计算解，而不是简单的递归。

解决递归中堆栈溢出的问题的一个思路就是使用动态规划（DP）技术，该技术建立在重用中间解的结果来计算终解的思想之上。

要计算

的值，首先要计算 n 之前的所有值，即

如果我们已经在某个地方保留了数字 n - k 的解，那么就不需要使用递归计算。

算法：

基于上述所说，我么可以在以下步骤实现 DP 解决方案。

几乎所有的动态规划解决方案，首先会创建一个一维或多维数组 DP 来保存中间子解的值，以及通常数组最后一个值代表最终解。注意，我们创建了一个虚构的元素 dp[0]=0 来简化逻辑，这有助于在在余数 (n-k）恰好是一个完全平方数的情况下。
我们还需要预计算小于给定数字 n 的完全平方数列表（即 square_nums）。
在主要步骤中，我们从数字 1 循环到 n，计算每个数字 i 的解（即 numSquares(i)）。每次迭代中，我们将 numSquares(i) 的结果保存在 dp[i] 中。
在循环结束时，我们返回数组中的最后一个元素作为解决方案的结果。
在下图中，我们演示了如何计算与 dp[4] 和 dp[5] 相对应的 numSquares(4) 和 numSquares(5) 的结果。

下面是示例实现，其中 Python 解决方案花费了约 3500 ms，这比当时 50% 的提交要快。

注意：以下 Python 解决方案仅适用于 Python2。出于某种未知的原因，Python3 运行相同的代码需要更长的时间。

Python 实现

class Solution(object): def numSquares(self, n): &34;&34;&34; square_nums = [i**2 for i in range(0, int(math.sqrt(n))+1)] dp = [float(&39;)] * (n+1) 34;&34; return: true if &34; can be decomposed into &34; number of perfect square numbers. e.g. n=12, count=3: true. n=12, count=2: false &34;& list of square numbers that are less than `n` square_nums = [i * i for i in range(1, int(n**0.5)+1)] level = 0 queue = {n} while queue: level += 1 which would even provide a 5-times speedup, 200ms vs. 1000ms. next_queue = set find the node! elif remainder < square_num: break else: next_queue.add(remainder - square_num) queue = next_queue return level

Java 实现

class Solution { public int numSquares(int n) { ArrayList<Integer> square_nums = new ArrayList<Integer>; for (int i = 1; i * i <= n; ++i) { square_nums.add(i * i); } Set<Integer> queue = new HashSet<Integer>; queue.add(n); int level = 0; while (queue.size > 0) { level += 1; Set<Integer> next_queue = new HashSet<Integer>; for (Integer remainder : queue) { for (Integer square : square_nums) { if (remainder.equals(square)) { return level; } else if (remainder < square) { break; } else { next_queue.add(remainder - square); } } } queue = next_queue; } return level; } }

复杂度分析

时间复杂度：

其中 h 是 N 元树的高度。在前面的方法三我们可以看到详细解释。

空间复杂度：

这也是在 h 级可以出现的最大节点数。可以看到，虽然我们保留了一个完全平方数列表，但是空间的主要消耗是队列变量，它跟踪给定 N 元树级别上要访问的剩余节点。

方法五：数学运算

随着时间的推移，已经提出并证明的数学定理可以解决这个问题。在这一节中，我们将把这个问题分成几个例子。

1770 年，Joseph Louis Lagrange证明了一个定理，称为四平方和定理，也称为 Bachet 猜想，它指出每个自然数都可以表示为四个整数平方和：

其中 a0,a1,a2,a3 表示整数。

例如，3，31 可以被表示为四平方和如下：

情况 1：拉格朗日四平方定理设置了问题结果的上界，即如果数 n 不能分解为较少的完全平方数，则至少可以分解为 4 个完全平方数之和，即

正如我们在上面的例子中可能注意到的，数字 0 也被认为是一个完全平方数，因此我们可以认为数字 3 可以分解为 3 个或 4 个完全平方数。

然而，拉格朗日四平方定理并没有直接告诉我们用最小平方数来分解自然数。

后来，在 1797 年，Adrien Marie Legendre用他的三平方定理完成了四平方定理，证明了正整数可以表示为三个平方和的一个特殊条件：

其中 k 和 m 是整数。

情况 2：与四平方定理不同，Adrien-Marie-Legendre 的三平方定理给了我们一个充分必要的条件来检验这个数是否只能分解成 4 个平方。

从三平方定理看我们在第 2 种情况下得出的结论可能很难。让我们详细说明一下推论过程。

首先，三平方定理告诉我们，如果 n 的形式是

那么 n 不能分解为 3 个平方的和。此外，我们还可以断言 n 不能分解为两个平方和，数本身也不是完全平方数。因为假设数 n 可以分解为

然后通过在表达式中添加平方数 0，即

我们得到了数 n 可以分解为 3 个平方的结论，这与三平方定理相矛盾。因此，结合四平方定理，我们可以断言，如果这个数不满足三平方定理的条件，它只能分解成四个平方和。

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

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

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

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

算法：

可以按照上面的例子来实现解决方案。

首先，我们检查数字 n 的形式是否为

如果是，则直接返回 4。

否则，我们进一步检查这个数本身是否是一个完全平方数，或者这个数是否可以分解为两个完全平方数和。

在底部的情况下，这个数可以分解为 3 个平方和，但我们也可以根据四平方定理，通过加零，把它分解为 4 个平方。但是我们被要求找出最小的平方数。

Python 实现

class Solution: def isSquare(self, n: int) -> bool: sq = int(math.sqrt(n)) return sq*sq == n def numSquares(self, n: int) -> int: reducing the 4^k factor from number if (n & 7) == 7: check if the number can be decomposed into sum of two squares for i in range(1, int(n**(0.5)) + 1): if self.isSquare(n - i*i): return 2 # bottom case from the three-square theorem return 3

Java 实现

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

复杂度分析

时间复杂度：