120. 三角形最小路径和
题目描述
思路分析
线性dp
原地覆盖，额外空间
O
(
1
)
O(1)
O(1)
如果不允许修改数组，那就用状态机dp
代码实现
class Solution {
public:
int minimumTotal(vector<vector<int>>& g) {
for(int i=g.size()-2;i>=0;i--){
for(int j=0;j<=i;j++){
g[i][j]+=min(g[i+1][j],g[i+1][j+1]);
}
}
return g[0][0];
}
};