首页 » 编程之美 » 正文

[leetcode_120]Triangle

简单DP一次AC,附上代码:

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        for(int i = triangle.size()-2;i >= 0; i--)
        {
            for(int j = 0;j < triangle[i].size();j++)
            {
                if(triangle[i][j] + triangle[i+1][j] < triangle[i][j] + triangle[i+1][j+1])
                {
                    triangle[i][j] = triangle[i][j] + triangle[i+1][j];
                }
                else
                {
                    triangle[i][j] = triangle[i][j] + triangle[i+1][j+1];
                }
            }
        }
        return triangle[0][0];
    }
};

发表评论