Java. DP. Short code and long code [62ms]


  • 0
    H
    //*
    //short code for nothing
    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; (i-j*j)>=0; j++)
                    dp[i] = Math.min(dp[i], dp[i-j*j]+1);
                
            return dp[n];
        }
    }
    
    /*/
    //easier to understand
    public class Solution {
        public int numSquares(int n) {
            int[] dp = new int[n+1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0]=0;
            
            //dp from 1
            for(int i=1; i<=n; i++){
                //check min { f(n-1), f(n-4), f(n-9),...., f(n-j^2) 
                int min = Integer.MAX_VALUE;
                for(int j=1; (i-j*j)>=0; j++){
                    min = Math.min(min, dp[i-j*j]+1);
                }
                dp[i]=min;	
            }
            
            return dp[n];
        }
    }
    //*/ 
    
    

Log in to reply
 

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