dp[n] = Min{ dp[n - i*i] + 1 }, for n - i*i >=0 && i >= 1
具体推理如下：
The most intuitive approach besides brute force would probably be dynamic programming, whether it's bottom up iteration or recursion with memoization, they all based on the recurrence relation:
j = i + (a perfect square number) or i = j + (a perfect square number)
已知起始点0,和终点n，这样问题就转化为一个最短路径问题。故使用BFS。
// Consider a graph which consists of number 0, 1,...,n as
// its nodes. Node j is connected to node i via an edge if
// and only if either j = i + (a perfect square number) or
// i = j + (a perfect square number). Starting from node 0,
// do the breadth-first search. If we reach node n at step
// m, then the least number of perfect square numbers which
// sum to n is m. Here since we have already obtained the
// perfect square numbers, we have actually finished the
// search at step 1.
Solution
Dynamic Programming - Iterative Bottom Up (~ 22ms AC)
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}
}
return dp[n];
}
}
DP another version
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for(int i = 1; i <= n; ++i) {
int min = Integer.MAX_VALUE;
int j = 1;
while(i - j*j >= 0) {
min = Math.min(min, dp[i - j*j] + 1);
j++;
}
dp[i] = min;
}
return dp[n];
}
}
Mathematical - (1ms AC)
class Solution {
// Based on Lagrange's Four Square theorem, there
// are only 4 possible results: 1, 2, 3, 4.
public int numSquares(int n)
{
// If n is a perfect square, return 1.
if(is_square(n))
{
return 1;
}
// The result is 4 if and only if n can be written in the
// form of 4^k*(8*m + 7). Please refer to
// Legendre's three-square theorem.
while ((n & 3) == 0) // n%4 == 0
{
n >>= 2;
}
if ((n & 7) == 7) // n%8 == 7
{
return 4;
}
// Check whether 2 is the result.
int sqrt_n = (int)(Math.sqrt(n));
for(int i = 1; i <= sqrt_n; i++)
{
if (is_square(n - i*i))
{
return 2;
}
}
return 3;
}
private boolean is_square(int num)
{
int sqrt_num = (int) Math.sqrt(num);
return sqrt_num * sqrt_num == num;
}
}
Recursion Memoization (NOT RECOMMENDED) - (655ms AC 4.86% percentile)
class Solution {
public int fun(Map<Integer,Integer> map, int target)
{
if(map.containsKey(target))
return map.get(target);
int temp = Integer.MAX_VALUE;
for(int i = 1; i<= (int)Math.sqrt(target); i++)
{
temp = Math.min(temp, fun(map,target - i*i)+1);
}
map.put(target, temp);
return temp;
}
public int numSquares(int n) {
int nums = (int)Math.sqrt(n);
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i = 1; i<= (int)Math.sqrt(n); i++)
{
map.put(i*i,1);
}
return fun(map,n);
}
BFS Version (~113ms 21.89%)
class Solution {
public int numSquares(int n) {
int numOfSquares = 0;
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.add(0);
visited.add(0);
while (!queue.isEmpty()) {
int size = queue.size();
numOfSquares++;
while (size > 0) {
int num = queue.poll();
for (int i = 1; i*i <= n; i++) {
int x = num + i*i;
if (x == n) {
return numOfSquares;
}
if (x > n) {
break;
}
if (!visited.contains(x)) {
queue.offer(x);
visited.add(x);
}
}
size--;
}
}
return numOfSquares;
}
}