基本思想是自底向上,但是又可以细分为两种方法:
- 空间复杂度O(n),优点是无需修改输入
- 空间复杂度O(1),优点是无需辅助空间
方法一
// // Created by jt on 2020/8/14. // #include <vector> using namespace std; class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { vector<int> dp(triangle[triangle.size() - 1]); for (int i = triangle.size() - 2; i >= 0; --i) { for (int j = 0; j <= i; ++j) { dp[j] = triangle[i][j] + min(dp[j], dp[j+1]); } } return dp[0]; } };
方法二
// // Created by jt on 2020/8/14. // #include <vector> using namespace std; class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { for (int i = triangle.size() - 2; i >= 0; --i) { for (int j = 0; j <= i; ++j) { triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]); } } return triangle[0][0]; } };