Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[ [2], [3,4], [6,5,7], [4,1,8,3] ]The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
题意：给定一个三角形，三角形每个位置都有一个权值；从顶部开始，每次只能走下一行相邻的位置，求到底部的最短权值之和。
分析：发现每一行第一个元素只能从上一行第一个元素走来，每一行的最后一个元素也只能从上一行最后一个元素走来，三角形对齐之后发现是上一行倒数第二个元素；其它位置都有两个方向走向它们，即前一行的当前位置和前一行前一个位置，求它们的最小值即可。
【2】
【3,4】
【6,5,7】
【4,1,8,3】
方法：采用自顶向下计算，求每一个位置的最小值，最后从最后一行中找出最小的值返回。
C++代码:
class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { int m=triangle.size(); for(int i=1;i<m;i++) { int j=triangle[i].size(); for(int k=0;k<j;k++) { if(!k) triangle[i][k]+=triangle[i-1][k]; else { if(k<=triangle[i-1].size()-1) triangle[i][k]+=min(triangle[i-1][k-1],triangle[i-1][k]); else triangle[i][k]+=triangle[i-1][k-1]; } } } int j = triangle[m-1].size(),MIN=100000; for(int k=0;k<j;k++) MIN = min(MIN,triangle[m-1][k]); return MIN; } };