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.
int minimumTotal(int** triangle, int triangleRowSize, int *triangleColSizes) { //add bottom to top if(triangleRowSize == 0) return 0; //memorize a triangleRowSize array int n = triangleRowSize - 1; // go over row for(int layer = triangleRowSize - 2; layer >= 0; layer--){ //go over col for(int i = 0; i <= layer; i++){ triangle[n][i] = (triangle[n][i] > triangle[n][i + 1] ? triangle[n][i + 1] : triangle[n][i] )+ triangle[layer][i]; } } return triangle[n][0]; }
原文：http://www.cnblogs.com/dylqt/p/5120600.html