给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。


例如，给定三角形：


[

[2],

[3,4],

[6,5,7],

[4,1,8,3]

]

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


说明：


如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

//使用一个一位数组，长度为最后一条边的长度classSolution{public:intminimumTotal(vector<vector<int>>&triangle){introws=triangle.size();if(rows==0){return0;}intcolumns=triangle[rows-1].size();vector<int>dp(columns,0);dp[0]=triangle[0][0];for(inti=1;i<rows;i++){for(intj=triangle[i].size()-1;j>=0;j--){if(j==triangle[i].size()-1){dp[j]=dp[j-1]+triangle[i][j];}elseif(j==0){dp[j]=dp[j]+triangle[i][j];}else{dp[j]=std::min(dp[j-1],dp[j])+triangle[i][j];}}for(inti=0;i<columns;i++){cout<<dp[i];}cout<<endl;}sort(dp.begin(),dp.end());returndp[0];}};