美文网首页
【leetcode】No.120:triangle

【leetcode】No.120:triangle

作者: I讨厌鬼I | 来源:发表于2019-07-27 17:05 被阅读0次

    题目描述

    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).
    Note:
    Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

    思路

    由于只能通过相邻的结点,就好像一棵完全二叉树,找到完全二叉树最小的路径我们用递归的方法可以这样做:选择左子节点和右子节点中最小的与当前值相加,再往上,层做同样的事。换成当前场景也是一样,我们可以从最底层自底向上去更新,最终到跟节点的值就是路径最小值,更新过程如下:

       [2],                 [2],              
      [3,4],              [3, 4],            [2],
     [6,5,7],     ==>   [7, 6, 10]     ==>  [9, 10]   ==>    [11]
    [4,1,8,3]
    

    代码

    import java.util.ArrayList;
    
    public class Solution {
        public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
            int len = triangle.size();
            for (int i=len-2; i>=0; i--){
                for (int j=0; j<=i; j++){
                    triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i+1).get(j), triangle.get(i+1).get(j+1)));
                }
            }
            return triangle.get(0).get(0);
        }
    }
    

    相关文章

      网友评论

          本文标题:【leetcode】No.120:triangle

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