# An easy understanding DP solution in Java

• dp[n] indicates that the perfect squares count of the given n, and we have:

``````dp[0] = 0
dp[1] = dp[0]+1 = 1
dp[2] = dp[1]+1 = 2
dp[3] = dp[2]+1 = 3
dp[4] = Min{ dp[4-1*1]+1, dp[4-2*2]+1 }
= Min{ dp[3]+1, dp[0]+1 }
= 1
dp[5] = Min{ dp[5-1*1]+1, dp[5-2*2]+1 }
= Min{ dp[4]+1, dp[1]+1 }
= 2
.
.
.
dp[13] = Min{ dp[13-1*1]+1, dp[13-2*2]+1, dp[13-3*3]+1 }
= Min{ dp[12]+1, dp[9]+1, dp[4]+1 }
= 2
.
.
.
dp[n] = Min{ dp[n - i*i] + 1 },  n - i*i >=0 && i >= 1
``````

and the sample code is like below:

``````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];
}
``````

Hope it can help to understand the DP solution.

• brilliant idea!

• Seems like O(n) space complexity. Is there no way to bring that down? What if n == MAX_INT?

• Of course you can just use O(1) space to solve this problem, you can refer to Lagrange's four-square theorem and try to find out a mathematical solution(in fact, there're some leetcoders using this), but in this case, if you insist on using DP to solve it, I don't think you can bring the space complexity down, here dp[n] doens't only depend on dp[n-1], you have to keep { dp[n - ii] + 1 , n - ii >=0 && i >= 1 } until you get the best dp[n].

• Can someone help us explain why the complexity is O(n)?
this is a sum of all square roots from 1 to n .. is this proven to be equivalent to O(n) ?

• got that .. just integrate sqrt(n) ~> (n^3/2) .. got confused thinking someone called this solution O(n) ..

• Why do you need Arrays.fill(dp, Integer.MAX_VALUE);? This solution runs just fine without this line.

• really nice idea!

• Nice solution!

Also I think Arrays.fill(dp, Integer.MAX_VALUE) isn't necessary here.

• What's the time complexity of this method. Very elegant and simple solution. I'm having trouble deriving time complexity. For each value of i, inner loop is running root of i times.
Ex: for 16 it will run for:
16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
4 4 4 4 4 4 4 3 3 3 3 3 2 2 2 1 (something like that)

Will it still be O(N) as some people have mentioned.

• @agrawalm
as some already said above, I think time complexity is O(n^1.5), space complexity is O(n)

• @benqiang
Actually some of the calculations could be ignored. E.g. if sqrt(n) - (int)sqrt(n) == 0 then we can set the value to 1 directly. If it isn't, then the least numbers should be greater or equal than 2. If ever meet 2, we can set the value to 2 directly.

• Thanks for sharing.

• @Karci
simplified solution

``````public 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];
}
}
``````

• Guys, does anyone know what's the time complexity of this solution?
Thanks a lot!

• @Karci Nice solution mate.. Thanks for sharing :)

• @MorganZhang1991
I think it's O(n^3/2)

• This is exactly the "Knapsack Problem"

• can someone explain the meaning of i-jj ? and why while i-jj >= 0 ?

• WHY

``````        for(int j = 1; j * j <= i; j++)
``````

skip those between j * j ~ (j + 1) * (j + 1) [as gap]

My solution is like this, trying to figure it out why we could skip the gap

``````public int numSquares(int n) {
int[] res = new int[n + 1];
Arrays.fill(res, Integer.MAX_VALUE);
res[0] = 1;
for (int i = 1; i <= n; i++) {
int root = (int)Math.sqrt(i);
if (root * root == i) {
res[i] = 1;
continue;
}
for (int j = 1; j <= i / 2; j++) {
// int subroot = (int)Math.sqrt(i - j);
// if (subroot * subroot == i - j) {
res[i] = Math.min(res[i], res[i - j] + res[j]);
// }
}
// System.out.println(res[i]);
}
return res[n];
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.