1. question: 完全平方数（中等）
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/perfect-squares
示例 1：
1
2
3
| 输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
|
示例 2：
1
2
3
| 输入：n = 13
输出：2
解释：13 = 4 + 9
|
提示：
2. answers
这道题是完全背包问题，并且是组合问题。和零钱对换是一样的思路，只不过本题的物品以相对含蓄的方式指明了。
可以先找出所有物品；也可以在遍历的时候，限制一下物品【因为在遍历的时候，会递归到那个空间，即自动加入了本完全平方数；而那个空间肯定也已经是最优值，也就是每次都是回退的是i*i，即这就相当于完全平方式了squares[i]】。
先找出所有物品方式的代码如下所示：
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
| public class Solution_0127 {
public int numSquares(int n) {
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if(Math.pow(i, 2) > n) break;
list.add((int) Math.pow(i, 2));
}
Integer[] squares = new Integer[1];
squares = list.toArray(squares);
int[] dp = new int[n + 1];
int max = Integer.MAX_VALUE;
Arrays.fill(dp, max);
for (int i = 0; i < dp.length; i++) {
if(i % squares[0] == 0) dp[i] = i / squares[0];
}
for (int i = 1; i < squares.length; i++) {
for (int j = 0; j < dp.length; j++) {
if(j >= squares[i] && dp[j-squares[i]] != Integer.MAX_VALUE) dp[j] = Math.min(dp[j], dp[j-squares[i]] + 1);
}
}
return dp[n];
}
public static void main(String[] args) {
System.out.println();
Solution_0127 s = new Solution_0127();
System.out.println(s.numSquares(13));
}
}
|
在遍历过程中限制元素的方法代码如下所示：
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
| public class Solution_0127_02 {
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
for (int i = 0; i < dp.length; i++) {
dp[i] = i;
}
for (int i = 2; i * i <= n; i++) {
for (int j = 0; j < dp.length; j++) {
if(j >= i * i && dp[i*i] != Integer.MAX_VALUE) dp[j] = Math.min(dp[j], dp[j - i*i] + 1);
}
}
return dp[n];
}
public static void main(String[] args) {
System.out.println();
Solution_0127_02 s = new Solution_0127_02();
System.out.println(s.numSquares(12));
}
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
