描述

给定一个正三角形数组，自顶到底分别有 1，2，3，4，5...，n 个元素，找出自顶向下的最小路径和。

每一步只能移动到下一行的相邻节点上，相邻节点指下行种下标与之相同或下标加一的两个节点。

数据范围：三角形数组行数满足 1 \le n \le 200 \1≤n≤200  ，数组中的值都满足 |val| \le 10^4 \∣val∣≤104 

例如当输入[[2],[3,4],[6,5,7],[4,1,8,3]]时，对应的输出为11，
所选的路径如下图所示：

示例1

输入： 
[[10]]
复制
返回值： 
10
复制

示例2

输入： 
[[2],[3,4],[6,5,7],[4,1,8,3]]
复制
返回值： 
11
复制
说明： 
最小路径是 2 ， 3 ，5 ， 1

示例3

输入： 
[[1],[-1000,0]]
复制
返回值： 
-999

class Solution {
public:
    //int func(vector<vector<int> >& triangle)
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param triangle int整型vector<vector<>> 
     * @return int整型
     */
    int minTrace(vector<vector<int> >& triangle) {
        // write code here
        int n = triangle.size();
        if (n == 0) return 0;
        // dp[i][j]代表自顶向下到[i][j]坐标时的最小路径和，其初值为INT最大值
        vector<vector<int>>dp(n+1, vector<int>(n+1, INT_MAX));
        // base case dp[0][0]是triangle[0][0]
        // 根据路径移动规则，[i][j]坐标只能从[i-1][j-1]或者[i-1][j]走下来
        // 最左侧没有[i-1][j-1]，只有[i-1][j]
        dp[0][0] = triangle[0][0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i-1][0] + triangle[i][0];
        }
        
        for (int i = 1; i < n; i++) {
            int m = triangle[i].size();
            for (int j = 1; j < m; j++) {
                //状态转移，[i][j]坐标只能从[i-1][j-1]或者[i-1][j]走下来，其最短路径为[i-1][j-1]或者[i-1][j]的最小值加上triangle[i][j]
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j];
            }
        }
        int res = INT_MAX;
        // 最短路径即最后一行上各元素的最小值
        for (int i = 0; i < n; i++) {
            res = min(res, dp[n-1][i]);
        }
        return res;
    }
};