56ms java dp solution


  • 0
    C
    public class Solution {
        public int numSquares(int n) {
            int square_root=1;
            int[] dp = new int[n+1];
            for(int i = 1;i<n+1;i++){
                if(i == square_root*square_root){
                    dp[i] = 1;
                    square_root+=1;
                }else{
                    int min = i;
                    for(int j = square_root-1;j>0;j--)
                        min = Math.min(min,1+dp[i-j*j]);
                    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.