120. 三角形最小路径和
2019-06-02 本文已影响0人
SunspotsInys
惯例，写贴代码
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];
}
};
- 解题思路：递推
- 这道题是经典的数字三角形题目，最简单的办法就是从下往上递推。
- 比如，站在第三行第一列，从这个点往下走的最小路径必然是第四行第一列和第二列中值最小的那一个。
- 每次递推修改一行的值，直到递推到第一行。
- 执行用时战胜 96.62 % 的 cpp 提交记录
