leecode第120题：

发表于 更新于 分类于

题目：给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
例如，给定三角形：

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
链接

解题思路：直观上，从三角形的顶部，每次选择下一步可选的位置中较小的值，直到三角形的底部位置，该路径就为最小路径。然而这是错误的，例如：

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,1],
  [4,1,8,3]
]

最小路径应为：2+4+1+3，而不是2+3+5+1。
正确的思路是：从底部往上计算，选择最后一行作为dp数组，从倒数第二行开始往上计算。dp[j]的含义为改位置到底部的最小距离，因此计算结束后，dp[0]就是所求的结果。

代码：

1
2
3
4
5
6
7
8
9
10
11
int minimumTotal(vector<vector<int>>& triangle) {
    int h = triangle.size();
    if (h==0) return 0;
    vector<int> dp = triangle.back();
    for (int i=h-2; i>=0; i--) {
        for (int j=0; j<triangle[i].size(); j++) {
            dp[j] = min(dp[j], dp[j+1]) + triangle[i][j];
        }
    }
    return dp[0];
}