JS solution beats 93%


  • 0
    L
    var minimumTotal = function(triangle) {
        if(triangle.length===1)
        return (typeof triangle[0][0]==='undefined')? Number.MAX_VALUE:triangle[0][0];
        var dp=[[]];
        dp[0][0]=triangle[0][0];
        for(var i=1;i<triangle.length;i++){
            dp[i]=new Array(triangle[i].length);
            dp[i][0]=dp[i-1][0]+triangle[i][0];
            for(var j=1;j<triangle[i].length-1;j++){
                dp[i][j]=Math.min(dp[i-1][j]+triangle[i][j],dp[i-1][j-1]+triangle[i][j]);
            }
            dp[i][j]=dp[i-1][j-1]+triangle[i][j];
        }
        return getMin(dp[dp.length-1]);
    };
    function getMin(nums){
        var min=nums[0];
        for(var i=0;i<nums.length;i++){
            if(nums[i]<min)
            min=nums[i];
        }
        return min;
    }
    

  • 0
    T

    Here is my O(n) space js code

    var minimumTotal = function (triangle) {
        const sum = [triangle[0][0]];
        for (let i = 1; i < triangle.length; i++) {
            sum[i] = sum[i - 1];
            for (let j = triangle[i].length - 1; j > 0; j--) {
                sum[j] = Math.min(sum[j], sum[j - 1]) + triangle[i][j];
            }
            sum[0] += triangle[i][0];
        }
    
        return Math.min(...sum);
    };
    

Log in to reply
 

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