279 Perfect Squares

1. Question

Given a positive integern, find the least number of perfect square numbers (for example,1, 4, 9, 16, ...) which sum ton.
For example, givenn=12, return3because12 = 4 + 4 + 4; givenn=13, return2because13 = 4 + 9.

2. Implementation

(1) BFS
1
class Solution {
2
public int numSquares(int n) {
3
int upperBound = (int)Math.sqrt(n);
4
int[] squares = new int[upperBound];
5
6
for (int i = 1; i <= upperBound; i++) {
7
squares[i - 1] = i * i;
8
}
9
10
Queue<Integer> queue = new LinkedList<>();
11
queue.add(0);
12
13
boolean[] visited = new boolean[n + 1];
14
int level = 0;
15
16
while (!queue.isEmpty()) {
17
int size = queue.size();
18
++level;
19
20
for (int i = 0; i < size; i++) {
21
int curNum = queue.remove();
22
visited[curNum] = true;
23
24
for (int square : squares) {
25
int nextNum = curNum + square;
26
27
if (nextNum > n) {
28
break;
29
}
30
else if (nextNum == n) {
31
return level;
32
}
33
else if (!visited[nextNum]) {
34
queue.add(nextNum);
35
}
36
}
37
}
38
}
39
return level;
40
}
41
}
Copied!
(2) DP
1
class Solution {
2
public int numSquares(int n) {
3
int[] dp = new int[n + 1];
4
Arrays.fill(dp, Integer.MAX_VALUE);
5
dp[0] = 0;
6
7
for (int i = 1; i <= n; i++) {
8
for (int j = 1; j <= (int)Math.sqrt(i); j++) {
9
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
10
}
11
}
12
return dp[n];
13
}
14
}
Copied!
(3) Memoization
1
public class Solution {
2
public int numSquares(int n) {
3
int[] cache = new int[n + 1];
4
return dfs(n, cache);
5
}
6
7
public int dfs(int n, int[] cache) {
8
if (n == 0) {
9
return 0;
10
}
11
12
if (n == 1) {
13
return 1;
14
}
15
16
if (cache[n] != 0) {
17
return cache[n];
18
}
19
20
int num = Integer.MAX_VALUE;
21
22
for (int i = 1; i * i <= n; i++) {
23
num = Math.min(num, dfs(n - i * i, cache) + 1);
24
}
25
cache[n] = num;
26
return num;
27
}
28
}
Copied!

3. Time & Space Complexity

BFS: 时间复杂度O(n * sqrt(n)), 空间复杂度O(n)
DP: 时间复杂度O(n * sqrt(n)), 空间复杂度O(n)
Memoization: 时间复杂度O(n * sqrt(n)), 空间复杂度O(n)