美文网首页
120. Triangle

120. Triangle

作者: exialym | 来源:发表于2016-11-16 16:23 被阅读10次

    Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
    For example, given the following triangle

    [
              [2], 
             [3,4], 
            [6,5,7], 
           [4,1,8,3]
    ]
    

    The minimum path sum from top to bottom is 11
    (i.e., 2 + 3 + 5 + 1 = 11).
    由于每次在下面一行选择时只能选和上面选中的相邻的,所以从上往下遍历,每一行每一个元素都取上一行与自己相邻的元素中最小的与自己相加,存在自己这里。遍历完后再遍历最后一行,找到最小的元素,就是我们要的最小和。

    var minimumTotal = function(triangle) {
        var row = triangle.length;
        var rec = [triangle[0][0]];
        for (let i = 1;i < row;i++) {
            for (let j = 0;j < triangle[i].length;j++) {
                if (j===0)
                    triangle[i][j] = triangle[i-1][j] + triangle[i][j];
                else if (j===triangle[i].length-1)
                    triangle[i][j] = triangle[i-1][j-1] + triangle[i][j];
                else {
                    if(triangle[i-1][j-1]>triangle[i-1][j])
                        triangle[i][j] = triangle[i-1][j] + triangle[i][j];
                    else
                        triangle[i][j] = triangle[i-1][j-1] + triangle[i][j];
                }
            }
        }
        var min = triangle[row-1][0];
        for (let i = 1;i < triangle[row-1].length;i++) {
            if (triangle[row-1][i]<min)
                min = triangle[row-1][i];
        }
        return min;
    };
    

    相关文章

      网友评论

          本文标题:120. Triangle

          本文链接:https://www.haomeiwen.com/subject/kperpttx.html