leetcode 116 三角形最短路径

class Solution {
public:
    int solu_sum;
    int solu_ans;
    int minimumTotal(vector<vector<int>>& triangle) {
    solu_ans = 0x7fffffff;
    solu_sum = 0;
    travel(0,0,triangle);
        return solu_ans;
    }
    int travel(int col, int row, vector<vector<int>>& triangle){
     solu_sum += triangle[row][col];
        if(row+1 >= triangle.size())
     {
         if(solu_sum < solu_ans)
             solu_ans = solu_sum;
        solu_sum -= triangle[row][col];
            return 0;
     }
        travel(col,row+1,triangle);
        travel(col+1,row+1,triangle);
        solu_sum -= triangle[row][col];
        return 0;
    }
};

超时！

class Solution {
public:
    vector<int> sum_tmp;
    int minimumTotal(vector<vector<int>>& triangle) {
        sum_tmp = triangle.back();
        for(int k = sum_tmp.size()-1; k > 0; --k){
            for(int i = 0; i < k; ++i){
                sum_tmp[i] = min(sum_tmp[i],sum_tmp[i+1]);
            }
            for(int i = 0; i < k; ++i){
                sum_tmp[i] += triangle[k-1][i];
            }
        }
        return sum_tmp[0];
    }

};