Java Dynamic Programming Approach


  • 0
    E
    public class Solution {
        public int numSquares(int n) {
            ArrayList<Integer>list=new ArrayList<Integer>();
            int k=1;
            while(k*k<=n){
                int p=k*k;
                if((int)Math.pow(p,0.5)==k){
                    list.add(p);
                }
                k++;
            }
            int dp[][]=new int[list.size()][n+1];
            for(int i=0;i<n+1;i++){
                dp[0][i]=i;
            }
            for(int i=1;i<list.size();i++){
                for(int j=0;j<n+1;j++){
                    if(list.get(i)>j){
                        dp[i][j]=dp[i-1][j];
                    }
                    else{
                        dp[i][j]=Math.min(dp[i][j-list.get(i)]+1, dp[i-1][j]);
                    }
                }
            }
            return dp[list.size()-1][n];
        }
    }
    

Log in to reply
 

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