题目
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
示例 1:
1
2
3
|
输入: n = 12
输出: 3
解释: 12 = 4 + 4 + 4.
|
示例 2:
1
2
3
|
输入: n = 13
输出: 2
解释: 13 = 4 + 9.
|
题解
看到这题就感觉跟找零钱那道题非常像，有一点区别是找零钱中直接限定了有哪些零钱，而这道题则是要找平方数，需要自己开方计算出范围。自己的实现代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
int numSquares(int n) {
int count = sqrt(n);
vector<int> dp(n + 1, n + 1);
dp[0] = 0;
for (int i = 0; i <= n; i++) {
for (int j = 1; j <= count; j++) {
int value = j * j;
if(value > i) break;
dp[i] = min(dp[i], dp[i - value] + 1);
}
}
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
|
public int numSquares(int n) {
Queue<Integer> queue = new LinkedList<>();
HashSet<Integer> visited = new HashSet<>();
int level = 0;
queue.add(n);
while (!queue.isEmpty()) {
int size = queue.size();
level++; // 开始生成下一层
for (int i = 0; i < size; i++) {
int cur = queue.poll();
//依次减 1, 4, 9... 生成下一层的节点
for (int j = 1; j * j <= cur; j++) {
int next = cur - j * j;
if (next == 0) {
return level;
}
if (!visited.contains(next)) {
queue.offer(next);
visited.add(next);
}
}
}
}
return -1;
}
|
广度优先需要利用到队列，通过队列一层层的计算，直到找到为0的节点，那么这个时候的层数便是最少的个数。广度优先与深度优先均会存在重复值的问题，因此要使用hash表将数据存储下来，避免重复计算，降低复杂度。