279. 完全平方数

🟠   🔖  广度优先搜索 数学 动态规划  🔗 力扣 LeetCode

题目

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Example 1:

Input: n = 12

Output: 3

Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13

Output: 2

Explanation: 13 = 4 + 9.

Constraints:

• 1 <= n <= 10^4

题目大意

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

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

解题思路

• 由拉格朗日的四平方定理可得，每个自然数都可以表示为四个整数平方之和。 其中四个数字是整数。四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。这给出了本题的答案的上界。
• n 的最少数量完全平方数之和，等于 n 减去任意一个比 n 小的完全平方数的最少数量完全平方数之和，再加一。
• dp[i] 表示i的完全平方和的最少数量，dp[i - j * j] + 1表示减去一个完全平方数 j 的完全平方之后的数量加 1 就等于dp[i]，只要在dp[i], dp[i - j * j] + 1中寻找一个较少的就是最后dp[i]的值。
• dp(i) = Math.min(dp[i], dp(i - j * j) + 1)

复杂度分析

• 时间复杂度: O(n* sqrt(n))，n 是输入的整数，需要循环 n 次，每次计算 dp 方程的复杂度 sqrt(n)
• 空间复杂度: O(n)，使用了一个长度为 n 的辅助数组。

代码

const square = (n) => {
	let dp = new Array(n).fill(0);
	for (let i = 1; i <= n; i++) {
		dp[i] = i; // 最坏情况是每次+1，如dp[3] = 1 + 1 + 1
		for (let j = 1; i - j * j >= 0; j++) {
			dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
		}
	}
	return dp[n];
};

相关题目

题号	标题	题解	标签	难度
204	计数质数		数组 数学 枚举 1+
264	丑数 II	[✓]	哈希表 数学 动态规划 1+
2787	将一个数字表示成幂的和的方案数		动态规划