Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
BFS
public class Solution {
public int numSquares(int n) {
if (n < 2) return n;
List<Integer> edges = new ArrayList<>();
for (int i = 1; i * i <= n; i++) {
edges.add(i*i);
}
Queue<Integer> queue = new LinkedList<>();
queue.offer(n);
int level = 0;
while (!queue.isEmpty()) {
level++;
int size = queue.size();
for (int i = 0; i < size; i++) {
int top = queue.poll();
System.out.println(top);
//neighbors
for (int edge : edges) {
if (top == edge) {
return level;
} else if (top < edge) {
break;
} else {
queue.offer(top - edge);
}
}
}
}
return level;
}
}
dp
//接龙型dp
public class Solution {
public int numSquares(int n) {
int[] record = new int[n+1];
for (int i = 0; i <= n; i++) {
record[i] = i;
for (int j = 1; j * j <= i; j++) {
record[i] = Math.min(record[i], record[i - j * j] + 1);
}
}
return record[n];
}
}
