31ms BFS and 110ms DP.

• Here, BFS starts from the numbers which we can reach by only one step to two steps, three steps etc. If we get our target number n in this process, the program is over. So we cut a lot of redundancy.

BFS:

``````public class Solution {
public int numSquares(int n) {
Queue<Integer> queue = new LinkedList();
int[] dp = new int[n+1];
for(int i=1; i*i<=n; i++){
if(i*i==n)  return 1;
dp[i*i] = 1;
queue.offer(i*i);
}

while(!queue.isEmpty()){
int curr = queue.poll();
for(int i=1; i*i<=n-curr; i++){
if(i*i==n-curr) {
return dp[curr]+1;
}else if(i*i<n-curr&&dp[i*i+curr]==0){
dp[i*i+curr] = dp[curr]+1;
queue.offer(i*i+curr);
}else if(i*i>n-curr){
break;
}
}
}
return dp[n];
}
}
``````

DP:

``````public class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
if(n==0) return 0;
dp[1] = 1;
for(int i=2; i<=n; i++){
for(int j=1; j*j<=i; j++){
if(dp[i]==0&&i-j*j>=0) dp[i] = dp[i-j*j]+1;
else if(dp[i]!=0&&i-j*j>=0) dp[i] = Math.min(dp[i-j*j]+1, dp[i]);
}
}

return dp[n];
}
}
``````

• In BFS method, this condition is necessary since we already set it in for loop.

``````else if(i*i>n-curr){
break;
}
``````

• @codecola unnecessary?

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