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.
class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { int n=triangle.size(); if(n==0) return 0; int minpath1[n]; int minpath2[n]; minpath1[0]=triangle[0][0]; int* min1=minpath1; int* min2; for(int i=1;i<n;i++) { if(min1==minpath1) min2=minpath2; else min2=minpath1; min2[0]=min1[0]+triangle[i][0]; min2[i]=min1[i-1]+triangle[i][i]; for(int j=1;j<i;j++) { int sum1=min1[j]+triangle[i][j]; int sum2=min1[j-1]+triangle[i][j]; min2[j]=sum1; if(sum2<sum1) min2[j]=sum2; } min1=min2; } int minvalue=min1[0]; for(int i=1;i<n;i++) if(min1[i]<minvalue) minvalue=min1[i]; return minvalue; } };
原文：http://www.cnblogs.com/erictanghu/p/3759657.html