C++刷leetcode（120. 三角形最小路径和）【动态规划】
题目描述：给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
例如，给定三角形：
[
,
,
,
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
说明：
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
int minimumTotal(vector<vector<int>>& input) {
int len = input.size();
int col = input.size();
if(len == 1) return *min_element(input.begin(), input.end());
vector<vector<int> > res(len, vector<int> (col, INT_MAX));
res = input;
for(int i = 1; i < len; i++){
res = input + res;
}
for(int i = 1; i < len; i++){
for(int j = 1; j < input.size(); j++){
res = min(res, res) + input;
}
}
return *min_element(res.begin(), res.end());
}
页:
[1]