31ms BFS and 110ms DP.


  • 2
    J

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

  • 0
    C

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

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

  • 0
    J

    @codecola unnecessary?


Log in to reply
 

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