my javascript solution using dymanic programming with closure, 146ms


  • 0
    C
    
    var numSquares = (function() {
            var arr = [0,1];
    
            function countSquares(n) {
                var last = Math.floor(Math.sqrt(n)),
                    result = [];
                for (var i = 1; i <= last; i++) {
                    result.push(Math.pow(i, 2));
                }
                return result;
            }
    
            return function(n) {
                if (n < arr.length) return arr[n];
                for (var j = arr.length; j <= n; j++) {
                    var minCount = Number.POSITIVE_INFINITY;
                    var squares = countSquares(j);
                    for (var k = 0; k < squares.length; k++) {
                        minCount = Math.min(minCount, arr[j - squares[k]] + 1);
                    }
                    arr[j] = minCount;
                }
                return arr[n];
            }
    
        })();
    

Log in to reply
 

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