題目（鏈接）
給定一個三角形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 <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 104
題解
思路：
- 動態規劃
- 由題意可知，如果正位于當前行的下標
i，那么下一步可以移動到下一行的下標i或i + 1，那么當前節點f[i][j]只可以從兩個位置轉移而來，分別是f[i - 1][j - 1]和f[i - 1][j]， - 特殊處理三角形的邊界：
（1）第一列不能由f[i - 1][j - 1]轉移而來，
（2）每一行的最后一列不能由f[i - 1][j]轉移而來，
解決問題：創建f陣列的時候多創建兩列(第一列和最后一列)并賦值正無窮，這樣，計算的時候就可以計算f[i - 1][j - 1]和f[i - 1][j]兩個位置，由于是正無窮，并不會影響最小值的計算，
樸素版code:
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
const int INF = 1e9;
int n = triangle.size();
int f[n + 10][n + 10];
// 創建f陣列
for (int i = 1; i <= n; i ++){
for (int j = 0; j <= n + 1; j ++){
f[i][j] = INF;
}
}
// 狀態轉移
f[1][1] = triangle[0][0];
for (int i = 2; i <= n; i ++){
for (int j = 1; j <= i; j ++){
f[i][j] = min(f[i - 1][j - 1] + triangle[i - 1][j - 1], f[i - 1][j] + triangle[i - 1][j - 1]);
}
}
// 計算最小值
int res = INF;
for (int i = 1; i <= n; i ++){
res = min(res, f[n][i]);
}
return res;
}
};
空間優化版code:
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
const int INF = 1e9;
int n = triangle.size();
int f[n + 10];
for (int j = 0; j <= n + 1; j ++){
f[j] = INF;
}
f[1] = triangle[0][0];
for (int i = 2; i <= n; i ++){
for (int j = i; j >= 1; j --){ // 滾動陣列，因為需要使用上一層計算的值，所以需要倒著計算
f[j] = min(f[j - 1] + triangle[i - 1][j - 1], f[j] + triangle[i - 1][j - 1]);
}
}
int res = INF;
for (int i = 1; i <= n; i ++){
res = min(res, f[i]);
}
return res;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/506023.html
標籤：其他