DP solution in Java


  • 3
    J
    public class Solution {
        public int numSquares(int n) {
            int[] min = new int[n+1];
            for(int i = 0;i <= n;i++){
                min[i] = 999999999;
            }
            min[0] = 0;
            List<Integer> m1 = new ArrayList<Integer>();
            
           for(int i = 1;i <= n;i++){
               if (i*i <= n){
                   m1.add(i*i);
               }
                
            }
            
            int[] psquare = new int[m1.size()];
            for(int i =0 ; i < m1.size(); i++){
                psquare[i] = m1.get(i);
            }
            
            for(int i = 1 ; i <= n ; i++ ){
                for(int j = 0 ; j < psquare.length; j++){
                    if(psquare[j] <= i && min[i-psquare[j]]+ 1 < min[i]){
                        min[i] = min[i-psquare[j]]+1;
                    }
                }
            }
            return min[n];
            
        }
    }

Log in to reply
 

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