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.
» Solve this problemBonus 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.
[解题思路]
一维DP。逐行扫描,每一个位置能取得的最小sum,是该元素上面两个能取得的最小sum中最小的那一个sum加上自己的值。只需要开一个数组重复利用就行了。
实现的时候,有些繁琐的地方,这个题比较好从下往上扫描。如果从上往下,其中minV的初始值问题就很头疼。
[Code]
1: int minimumTotal(vector<vector<int> > &triangle) {
2: int row = triangle.size();
3: if(row ==0) return 0;
4: vector<int> minV(triangle[row-1].size());
5: for(int i =row-1; i>=0; i--)
6: {
7: int col = triangle[i].size();
8: for(int j =0; j<col; j++)
9: {
10: if(i == row-1)
11: {
12: minV[j] = triangle[i][j];
13: continue;
14: }
15: minV[j] = min(minV[j], minV[j+1]) + triangle[i][j];
16: }
17: }
18: return minV[0];
19: }
No comments:
Post a Comment