LeetCode_127_PerfectSquares


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

提示:

1
1 <= n <= 104

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) {

// 得到[1,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);

// 第一个物品是1,所以该物品可以在任何容量下都使的条件成立
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)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录