题目描述

给定一个三角形，找到从上到下的最小路径和，在每一步可以移动到下一行的相邻数字。

相邻的结点:

在这里指的是```下标```与```上一层结点下标```相同或者等于```上一层结点下标+ 1```的两个结点。

样例

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

输出11 (2 + 3 + 5 + 1 = 11).

C++ 代码

class Solution {
public:
    int minimumTotal(vector<vector<int>>& nums) {
        int n=nums.size();
        vector<vector<long long>> dp(2,vector<long long>(n));
        dp[0][0]=nums[0][0];
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<=i;j++)
            {
                dp[i&1][j]=INT_MAX;
                if(j>0)dp[i&1][j]=min(dp[i&1][j],dp[i-1&1][j-1]+nums[i][j]);
                //排除最左边：最左边不能从左上角过来
                if(j<i)dp[i&1][j]=min(dp[i&1][j],dp[i-1&1][j]+nums[i][j]);
                //排除最右边：最右边不能从正上面过来
            }
        }
        long long ans=INT_MAX;
        for(int i=0;i<n;i++)ans=min(ans,dp[n-1&1][i]);
        return ans;
    }
};