leetcode 120- triangle

例子：
[
[2], ------选中2
[3,4],------选中3
[6,5,7],------选中5
[4,1,8,3]------选中1
]
解释：首先不是选取每一行中最小的数值，而是选中相邻位置的最小数。例如：如果在第三行选中5，在第五行只能在1 8之中选择最小的。
如果这样解释此题就很容易想到DP：动态规划

• 算法的基本思想：
  题目说是从上到下，但是这个方向很难控制下一层那个位置是最小的数值，所以采用从下到上。
  设置DP数组，大小为4（根据上面的例子），首先加入最后一行的全部数值。

  
  图片.png

• 代码：
  C++:

int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();
    vector<int> dp(triangle.back());
    for (int i = n - 2; i >= 0; --i) {
        for (int j = 0; j <= i; ++j) {
            dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
        }
    }
    return dp[0];
}

JAVA:

public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        List<Integer> dp=new ArrayList<Integer>(triangle.get(triangle.size()-1));
        for (int i = n - 2; i >= 0; --i) {
            for (int j = 0; j <= i; ++j) {
                dp.set(j, Math.min(dp.get(j), dp.get(j+1)) + triangle.get(i).get(j));
            }
        }
        return dp.get(0);
    }