Monday, November 24, 2014

[LeetCode] Triangle

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.

思路:

这题用到了一点DP的思路,即存储每一层的结果,来计算下一层。关键点在于要用O(n) space。用两个数组prePath和curPath分别存储上一层和本层的每个坐标的min path sum。如果已知prePath,则可以计算curPath:

1. 对第j层 (j = 0 ~ n-1),一共有j+1个数:0:j。而上一层有j个数:0:j-1
2. 除去头尾两个数外,curPath[i] = min(prePath[i-1], prePath[i]) + triangle[j][i]
3. 头尾的特殊情况:curPath[0] = prePath[0] + triangle[j][0];curPath[j] = prePath[j-1] + triangle[j][j]
4. 在计算下一层前,需要交换curPath和prePath。
5. 在最后一层curPath计算结束后,在其中找一个最小值即为整个树的min path sum。

额外存储空间是2n。尽管通过滚动数组也可以事先n,但代码要复杂很多,面试短时间内容易出错。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        if(triangle.empty()) return 0;
        int n = triangle.size();
        vector<int> curPath(n,INT_MAX);
        vector<int> prePath(n,INT_MAX);
        curPath[0] = triangle[0][0];
        
        for(int lvl=1; lvl<n; lvl++) {
            prePath = curPath;
            curPath[0] = prePath[0] + triangle[lvl][0];
            curPath[lvl] = prePath[lvl-1] + triangle[lvl][lvl];
            for(int i=1; i<lvl; i++)
                curPath[i] = min(prePath[i-1], prePath[i]) + triangle[lvl][i];
        }
        
        int minPath = INT_MAX;
        for(int i=0; i<n; i++) 
            minPath = min(minPath, curPath[i]);
        
        return minPath;
    }
};

1 comment:

  1. 如果从底部开始计算,好像代码会简洁不少,当然也是用到了滚动数组

    class Solution {
    public:
    int minimumTotal(vector>& triangle) {
    if(triangle.size()<1) return 0;

    vector tmp=triangle[triangle.size()-1];
    for(int i=int(triangle.size())-2;i>=0;i--){
    for(int j=0;j<triangle[i].size();j++){
    tmp[j]=min(tmp[j],tmp[j+1])+triangle[i][j];
    }
    //tmp.pop_back();
    }

    return tmp[0];
    }

    ReplyDelete