简单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]; } };