Triangle

https://leetcode.com/problems/triangle/
三角形的数组问题
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).

题目解析

题目意思很清楚，给定一个三角形（这个三角形是一个二维数组），求出从三角形的顶部到底部相邻数字的最小和集。

乍一看这个题目加上这个例子，容易陷入一个误区：从上往下遍历这个三角形的行数，找出上一行的最小值，和下一行相邻的两个值，下一行的两个值找出最小的那个，依次类推，能够找到整个三角形的最小和，就像题目给出的那个结果一样。
但是，这是一个错误的思路

举一个反例：

Input:
[[-1],[2,3],[1,-1,-3]]
Output:
0
Expected:
-1

如果用上面的思路，会出现结果为0（1->2->-1）,但是实际本题的结论是(-1->3->-3)，
那么此时容易陷入第二个误区，也不算误区，算一个思路，暴力穷举，把每一种情况都穷举出来，找出最小的值。思路是没问题的，但是有没有更好的办法。

解题思路

为了得到一个全局最小的值，是时候献出我们的DP大法，找出每一个点对应的最小值

DP方法1

从上往下DP,每一个坐标(i,j)只能从他上面两个左边走下来，(i-1,j-1)和(i-1,j)，所以选出(i-1,j-1),(i-1,j)两个点中较小的那个，就是走到（i,j）这个点的数据了
dp[i][j] = min(dp[i-1][j-1],dp[i-1][j])
参考链接
这种实现的代码没有自己实现一遍，就看了下

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        for (int i = 1; i < triangle.size(); ++i) {
            for (int j = 0; j < triangle[i].size(); ++j) {
                if (j == 0) {
                    triangle[i][j] += triangle[i - 1][j];
                } else if (j == triangle[i].size() - 1) {
                    triangle[i][j] += triangle[i - 1][j - 1];
                } else {
                    triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);
                }
            }
        }
        return *min_element(triangle.back().begin(), triangle.back().end());
    }
};

DP方法2

从下往上进行DP，
递推公式是： dp[i][j] = dp[i+1][j] + dp[i+1][j+1] ，当前这个点的最小值，由他下面那一行临近的2个点的最小值与当前点的值相加得到。
只需要一个一维数组即可,例如在三角形的最后一行，dp[j]表明该行的第i列对应的最小值，所以此时的状态转移方程是:
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];

  //递推公式：dp[i][j] = dp[i+1][j] + dp[i+1][j+1]
    public int mininumTotal2(List<List<Integer>> triangle) {
        if (triangle.size() == 1) {
            return triangle.get(0).get(0);
        }
        int[] dp = new int[triangle.size()];

        //根据最后一行的数字进行初始化
        for (int i = 0; i < triangle.get(triangle.size() - 1).size(); i++) {
            dp[i] = triangle.get(triangle.size() - 1).get(i);
        }

        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }

这个方法有一个实例：

     -1

    2   3

  1  -1  -3

5   3   -1   2

DP计算过程
DP：5  3  -1  2

DP：4  3  -1  2

DP：4  -2  -1  2

DP：4  -2  -4  2

DP：0  -2  -4  2

DP：0  -1  -4  2

DP：-2  -1  -4  2