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.

 

Ref:http://www.cnblogs.com/feiling/p/3269609.html

[解题思路]

该题是经典的DP问题，状态可以定义成dp[node]表示从当前node到bottom的最小路径和，对于最下面一层，因为它们是最底层，故它们到bottom的最小路径和就是它们自身；再往上一层，如节点6，它到达bottom的最小路径和即为节点4与节点1之间的最小值加上节点6自身的值

由以上分析得出状态迁移方程：

dp[node] = value[node] + min(dp[child1], dp[child2])

另外本题要求时间复杂度为：O(n), n为三角形的行数

 

逐行扫描，每一个位置能取得的最小sum，是该元素上面两个能取得的最小sum中最小的那一个sum加上自己的值。只需要开一个数组重复利用就行了。

实现的时候，有些繁琐的地方，这个题比较好从下往上扫描。如果从上往下，其中minV的初始值问题就很头疼。

 

public class Solution {    public int minimumTotal(ArrayList
     
      
       > triangle) {        if(triangle == null || triangle.size() == 0){            return 0;        }        int row = triangle.size();        int[] num = new int[row];        for(int i = row-1; i>= 0; i--){            int col = triangle.get(i).size();            for(int j = 0; j< col; j++){                if(i == row-1){                    num[j] = triangle.get(i).get(j);                    continue;                }                num[j] = Math.min(num[j] , num[j+1])+ triangle.get(i).get(j);            }        }     return num[0];       }}