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.
动态规划，填格子。空间不是问题。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 |
class
Solution {public: int
minimumTotal(vector<vector<int> > &triangle) { vector<vector<int> >path (triangle); for(int
i = 1 ; i < triangle.size();i++) { for(int
j = 0 ; j <=i ; j ++) { if(j <= i-1 && j > 0) path[i][j] = min(path[i-1][j-1],path[i-1][j])+triangle[i][j]; else
if(j > i-1 && j!=0) path[i][j] = path[i-1][j-1]+triangle[i][j]; else
path[i][j]= path[i-1][j] +triangle[i][j]; } } int
min = path[triangle.size()-1][0]; for(int
i = 1 ; i < triangle.size();i++) { if(path[triangle.size()-1][i] < min)min = path[triangle.size()-1][i]; } return
min; }}; |
原文：http://www.cnblogs.com/pengyu2003/p/3611697.html