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.

##解题思路
该题是求解从顶到底中和最短的路径长度。我们可以发现，第i层中第j个元素，它所在的路径只能为第i-1层中第j个元素和第j-1个元素。因此后层的最小路径值必然和上一层的最小路径值有关。所以这里可以使用动态规划进行求解。

首先定义维护量dp[i]:表示从顶到当前层第i个节点的最小路径长度
则下一层可以表示为：
dp[i]=num[i]+Math.min(dp[i],dp[i-1]);   i=1...row-1 这里不包括第一个和最后一个节点

然而如果对每一行从前往后计算，会造成dp[i]被覆盖的问题，因此只能从后往前计算.
当求到最后一行的时候，会得到每个节点的dp值，然后取一个最小的就是从顶到底的所有路径中的最小和。

这里采用常量的DP空间来保存中间求解的路径值，符合只是用线性的扩展空间。

##算法代码
代码采用JAVA实现：

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

 public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle==null || triangle.size()==0)
        	return 0;
        int numRows=triangle.size();
        //定义维护量
        int[] dp=new int[numRows];
        dp[0]=triangle.get(0).get(0);//放入第一个元素
        for(int i=1;i<numRows;i++)
        {
        	//特殊处理第一个节点
        	dp[i]=triangle.get(i).get(i)+dp[i-1];
        	//从后往前依次遍历
        	for(int j=i-1;j>0;j--)
        	{
        		dp[j]=triangle.get(i).get(j)+Math.min(dp[j],dp[j-1]);
        	}
        	//特殊处理最后一个节点
        	dp[0]=triangle.get(i).get(0)+dp[0];
        }
        //得到最后一行每个节点的DP,求取最小值
        int min=dp[0];
        for(int i=1;i<dp.length;i++)
        {
        	if(dp[i]<min)
        		min=dp[i];
        }
        return min;
    }
}