By

文章目录

leetcode地址：https://leetcode.com/problems/triangle/

Problem:
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
		int[][] sums=new int[triangle.size()][triangle.size()];
		List<Integer> rows;
        int ret=0,column;
        
        
        if(triangle.size()>0)
	    {
        	for(int i=triangle.size()-1;i>=0;i--)
        	{
        		rows=triangle.get(i);
        		
        		if(i==triangle.size()-1)
        		{
        			//the last rows
        			for(int j=0;j<rows.size();j++)
        			{
        				sums[i][j]=rows.get(j);
        			}
        		}else{
        			
        			for(int j=0;j<rows.size();j++)
        			{
        				
        				sums[i][j]=this.getMin(rows.get(j)+sums[i+1][j],rows.get(j)+sums[i+1][j+1]);
        			}
        		}
        		
        	}
        	
        	ret=sums[0][0];
	    }
        
        return ret;
        
    }
	
	public Integer getMin(Integer a,Integer b)
	{
		return a>b?b:a;
	}
}

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录