Easy-to-Understand Java DP solution, 50ms, beats 94.8%


  • 0
    K
    public class Solution {
        public int numSquares(int n) {
            if(n < 4) return n;
            int[] results = new int[n+1];
            results[0] = 0;
            int cur = 0;
            for(int i = 1; i <= n; i++){
                if(i == (cur + 1) * (cur + 1)){
                    results[i] = 1;
                    cur++;
                }else results[i] = 1 + minRes(results, cur, i);
            }
    
            return results[n];
        }
        
        public int minRes(int[] results, int cur, int i){
            int minRes = Integer.MAX_VALUE;
            for(int j = 1; j <= cur; j++){
                if (results[i - j * j] < minRes) minRes = results[i - j*j];
            }
            return minRes;
        }
    }
    

Log in to reply
 

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