三角形最小路径和

[JesseZhao1990]

/**
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    for(var j= triangle.length;j>1;j--){
        for(var i=0;i<j-1;i++){
            var rootValue = triangle[j-2][i];
            var leftValue = triangle[j-1][i];
            var rightValue = triangle[j-1][i+1];
            var minValue = getMin(rootValue+leftValue,rootValue+rightValue);

            triangle[j-2][i] = minValue;
        }
    }
    return triangle[0][0]
    
};

function getMin(left,right){
    return left<=right? left:right;
}

方法二：
递归的写法,此种方法效率不高，有重复的计算。

function minimumTotal(triangle){
    
    function loop(triangle,n,index){
        if(n==triangle.length-1){
            return triangle[n][index];
        }
        var left = loop(triangle,n+1,index)+triangle[n][index];
        var right = loop(triangle,n+1,index+1)+triangle[n][index];
        return Math.min(left,right);
    }

    return loop(triangle,0,0)
}

var triangle = [
    [2],
   [3,4],
  [6,5,7],
 [4,1,8,3]
];

console.log(minimumTotal(triangle))

leetcode原题地址：https://leetcode-cn.com/problems/triangle/description/