首页 > 代码库 > [leetcode]Triangle

[leetcode]Triangle

Triangle

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.

算法思路:

思路1:

自上而下,用一个数组记录从根节点到第 i 层的所有节点的加权之后的情况,跌倒到最后一层时,即可求出最短路径。需要O(n)空间。

不再实现

 

思路2:

 1     public int minimumTotal(List<List<Integer>> triangle) { 2         if(triangle == null || triangle.size() == 0) return 0; 3         int height = triangle.size(); 4         for(int i = height - 2; i >= 0; i--){ 5             List<Integer> list = triangle.get(i); 6             for(int j = 0; j < list.size();j++){ 7                 int min = triangle.get(i + 1).get(j) < triangle.get(i + 1).get(j + 1) ? triangle.get(i + 1).get(j) : triangle.get(i + 1).get(j + 1);   8                 list.set(j, list.get(j) + min); 9             }10         }11         return triangle.get(0).get(0);12     }

这代码是之前看到的,很厉害。