30. 三角形最小路径和

题目

解析

1. 最小路径就是和相邻的两行有关系
2. 由于，从上往下有些麻烦，所以，从下往上
3. 首先，把最后一行的数据，存入 vector<int> f 中，并且 vector<int> g 保存：两行中，上面一行与下面相邻两个元素相加之和的最小数组
   1. 比如：以最后两行为例
   2. f 此时为 [4, 1, 8, 3]
      g 此时为 [0, 0, 0, 0]
   3. 然后，g 就更新为 [7, 6, 10, 0]
   4. f 也就更新为 g，即为： [7, 6, 10, 0]
   5. 依次类推
4. 最后，f[0]就是，第一个数，与下面最小的数相加的和，即为最短路径

• PS：

1. 如果不懂，就自己调试一下吧
2. 这里是动态规划，更新的是g和f（首先更新g，接着将g赋值给f）
3. 其中f，总是为最后一行最小数的数组：
   1. 比如：一开始为 [4, 1, 8, 3] ，后来状态转移为：[7, 6, 10, 0]
   2. 那么 [7, 6, 10, 0] 可以看成最后一行（替换后面两行，依次类推）

代码

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

• 简化

int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();
    vector<int> f(triangle[n - 1].begin(), triangle[n - 1].end());

    for(int i = n - 2; i >= 0; i--) {
        for(int j = 0; j <= i; j++) {
            f[j] = min(f[j], f[j + 1]) + triangle[i][j];
        }

    }
    return f[0];
}

PS：

1. 相比于上面的代码，下面的代码删除了 g
2. 原因：因为 f[j] 改变，对 f[j + 1] 并没有影响，所以就不需要 g 了。