题目内容

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例

示例 1：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：

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

示例 2：

输入：triangle = [[-10]]
输出：-10

提示

1、1 <= triangle.length <= 200
2、triangle[0].length == 1
3、triangle[i].length == triangle[i - 1].length + 1
4、-10^4 <= triangle[i][j] <= 10^4

题解

本题考查动态规划。

1、状态表示

设F[i][j] 表示所有从最后一行走到(i,j)点的路径的全局最小值。

2、状态计算

每一个点下方均有两条路径能够到达，一条是从(i+1,j)处向上到;另一条是从(i+1,j+1)处到，因此有以下递推关系式：

F[i][j] = min(F[i+1][j],F[i+1][j+1]) + 当前点的值

代码

class Solution {
public:
    int minimumTotal(vector<vector<int>>& f) {
        for(int i = f.size() - 2;i>=0;i--){//不算最后一层
            for(int j = 0;j<=i;j++){
              	//从最后一层开始，然后往前计算。每次计算，变更的是对应的下一层的内容，没有改变对应点本层的值。
                f[i][j] += min(f[i+1][j],f[i+1][j+1]); 
            }
        }
        return f[0][0];
    }
};