leetcode_triangle

发表于

难度：Medium

解题思路：简单的做法是从顶到底，递归的调用函数，得到最小路径值，但这样会超时。使用动态规划，令ret[i][j]为从顶到第i行，第j列的元素的最小路径。
则

ret[i][j] = min(ret[i-1][j-1]+triangle[i][j], ret[i-1][j-1]+triangle[i][j])

对于j=0,j=i-1的情况，只有一条路径，要做特殊处理。

代码如下：

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) {
        vector<vector<int>> ret = triangle;
        for(int i = 1; i < triangle.size();i++)
        {
            ret[i][0] = ret[i-1][0]+triangle[i][0];
            ret[i][i] = ret[i-1][i-1]+triangle[i][i];
            // cout<<ret[i][0]<<" "<<ret[i][i]<<endl;
            for(int j = 1; j < i; j++)
            {
                ret[i][j] = min(ret[i-1][j-1]+triangle[i][j], ret[i-1][j]+triangle[i][j]);
                // cout<<ret[i][j]<<endl;
            }
        }
        int minim = INT_MAX;
        int length = triangle.size();
        for(int j = 0; j < length;j++)
        {
            minim = min(ret[length-1][j],minim);
        }
        return minim;
    }
};

运行结果：6ms，超过29.69%