[LeetCode] 279. Perfect Squares

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 <= 104

完全平方数。

给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/perfect-squares
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

题意是给一个数字 N,请你返回最少的需要几个完全平方数的加和的个数。比如第一个例子,12 是由三个 4 组成,4 也是完全平方数。

思路是动态规划。首先说一下暴力解,这个题的暴力解是从 1 到 N 一个个看这个数字本身是否是一个完全平方数,如果 N 本身就是完全平方数,那么结果自然是 1;如果 N 不是完全平方数,那么可以试着从 1 开始,用 N 减去每个数的平方,看看需要几个完全平方数才能得到 N。举个例子,比如找 15 好了,第一个完全平方数是 1,需要 15 个 1;第二个完全平方数是 4,需要 3 个 4 + 3 个 1 = 一共 6 个数字。

其实动态规划的思路是从暴力解延伸出来的,只是我们用了一个额外的数组记录了之前的结果。首先创建一个长度为 N + 1 的数组记录 dp 的结果,并且 dp[0] = 1。从 i = 1 开始,一直遍历到 N。当遇到一个新的数字 N 的时候,需要再次从 1 开始遍历,看看当前的这个数字 i 是否整体或者部分能被某一个更小的数的平方代替。比如遍历到 7 的时候,我们发现 7 是可以被一个 2 的平方和三个 1 的平方代替的,所以 DP 的转移方程是

dp[i] = Math.min(dp[i], dp[i - j * j] + 1);

这里j的范围是[1, i)
最后返回的是dp[n]

复杂度

时间O(n)
空间O(n)

代码

Java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
for (int i = 0; i <= n; i++) {
dp[i] = i;
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}

JavaScript实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @param {number} n
* @return {number}
*/
var numSquares = function (n) {
let dp = new Array(n + 1).fill(0);
for (let i = 0; i <= n; i++) {
dp[i] = i;
for (let j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
};

[LeetCode] 279. Perfect Squares
https://shurui91.github.io/posts/2932573575.html
Author
Aaron Liu
Posted on
June 28, 2020
Licensed under