https://leetcode-cn.com/problems/triangle/solution/san-jiao-xing-zui-xiao-lu-jing-he-by-leetcode-solu/
-
三角形最小路徑和
給定一個三角形 triangle ,找出自頂向下的最小路徑和。
每一步隻能移動到下一行中相鄰的結點上。相鄰的結點 在這裡指的是 下标 與 上一層結點下标 相同或者等于 上一層結點下标 + 1 的兩個結點。也就是說,如果正位于目前行的下标 i ,那麼下一步可以移動到下一行的下标 i 或 i + 1 。
示例 1:
輸入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
輸出:11
解釋:如下面簡圖所示:
2
3 4
6 5 7
4 1 8 3
自頂向下的最小路徑和為 11(即,2 + 3 + 5 + 1 = 11)。
示例 2:
輸入:triangle = [[-10]]
輸出:-10
提示:
1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<vector<int>> f(n, vector<int>(n));
f[0][0] = triangle[0][0];
for (int i = 1; i < n; ++i) {
f[i][0] = f[i - 1][0] + triangle[i][0];
for (int j = 1; j < i; ++j) {
f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
}
f[i][i] = f[i - 1][i - 1] + triangle[i][i];
}
return *min_element(f[n - 1].begin(), f[n - 1].end());
}
};