279\. 完全平方数
# 279. 完全平方数 (opens new window)
# Description
Difficulty: 中等
Related Topics: 广度优先搜索 (opens new window), 数学 (opens new window), 动态规划 (opens new window)
给你一个整数 n
,返回 和为 n
的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1
、4
、9
和 16
都是完全平方数,而 3
和 11
不是。
示例 1:
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4
1
2
3
2
3
示例 2:
输入:n = 13
输出:2
解释:13 = 4 + 9
1
2
3
2
3
提示:
- 1 <= n <= 104
# Solution
Language: JavaScript
方法一:动态规划
思路及算法
我们可以依据题目的要求写出状态表达式:f[i] 表示最少需要多少个数的平方来表示整数 i。
dp[0] = 0
dp[1] = min(dp[0] + 1) = 1
dp[2] = min(dp[1] + 1) = 2
dp[3] = min(dp[2] + 1) = 3
dp[4] = min(dp[3] + 1, dp[0] + 1) = 1
dp[5] = min(dp[4] + 1, dp[1] + 1) = 2
最后的dp[n]为最终结果。
/**
* @param {number} n
* @return {number}
*/
var numSquares = function(n) {
const f = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
let minn = Number.MAX_VALUE;
for (let j = 1; j * j <= i; j++) {
minn = Math.min(minn, f[i - j * j]);
}
f[i] = minn + 1;
}
return f[n];
};
/**
* @param {number} n
* @return {number}
*/
var numSquares = function(n) {
const dp = [...Array(n+1)].map(_=>0); // 数组长度为n+1,值均为0
for (let i = 1; i <= n; i++) {
dp[i] = i; // 最坏的情况就是每次+1
for (let j = 1; i - j * j >= 0; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1); // 动态转移方程
}
}
return dp[n];
};
// 先遍历物品,再遍历背包
var numSquares1 = function(n) {
let dp = new Array(n + 1).fill(Infinity)
dp[0] = 0
for(let i = 0; i <= n; i++) {
let val = i * i
for(let j = val; j <= n; j++) {
dp[j] = Math.min(dp[j], dp[j - val] + 1)
}
}
return dp[n]
};
// 先遍历背包,再遍历物品
var numSquares2 = function(n) {
let dp = new Array(n + 1).fill(Infinity)
dp[0] = 0
for(let i = 1; i <= n; i++) {
for(let j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i - j * j] + 1, dp[i])
}
}
return dp[n]
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62