Leetcode_120 三角形中的最小路径

题目如下：
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

这一题是关于三角形的最小路径和，前两天做二叉树的题目，想要用递归做，但是没有思考出结果，就写了回溯法暴力遍历，然而TLE了，代码如下，思路很简单，遍历每一条路径，到底就更新最小路径和。

class Solution {
    private int res = Integer.MAX_VALUE;
    private int sum = 0;
    private int row_size;
    private int column_size;
    public int minimumTotal(List<List<Integer>> triangle) {
        //ll = new ArrayList<Integer>();
        row_size = triangle.size();
        if (row_size==0) return 0;
        column_size = triangle.get(row_size-1).size();
        dfs(triangle,0,0);        
        return res;        
    }
    private void dfs(List<List<Integer>> triangle, int row_index, int column_index){
        if (row_index<row_size){
            sum += triangle.get(row_index).get(column_index);
            if (row_index == row_size-1)
                res = (sum<res)?sum:res;
            dfs(triangle,row_index+1,column_index);
            dfs(triangle,row_index+1,column_index+1);
            sum -= triangle.get(row_index).get(column_index);}
    }
}

题目相关话题是DP，但是好半天也没想出来DP怎么写，搜到了大神的代码，参考自https://blog.csdn.net/liuchonge/article/details/70209533。

    public int minimumTotal(List<List<Integer>> triangle) {
        int row = triangle.size();
        int [] res = new int[row+1];
        for (int i=row-1; i>=0; i--){
            List<Integer> tmp = triangle.get(i);
            for(int j=0; j<tmp.size(); j++)
                res[j] = Math.min(res[j], res[j+1]) + tmp.get(j);
        }
        return res[0];
    }

看了代码就觉得其实很简单，从下往上更新每一行每个位置的最小路径值，更新到第一行就是全局最小路径值了，非常简洁。
执行用时: 4 ms, 在Triangle的Java提交中击败了100.00% 的用户
好的思路在于积累，继续努力啊。