120. Triangle
給定一個三角形數組，返回從頂部到底部的最小路徑和。
在每一步中，你可以移動到下一行的相鄰數字。更具體地說，如果你在當前行的索引 i，你可以移動到下一行的索引 i 或 i + 1。
範例：
輸入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 輸出：11 解釋：該三角形如下所示：
Python
from typing import List
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
# Start from the second last row and move upwards
for row in range(len(triangle) - 2, -1, -1):
for col in range(len(triangle[row])):
# Update the current value to the minimum path sum
triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1])
# The top element now contains the minimum path sum
return triangle[0][0]
17.6MB, 62ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
// Start from the second last row and move upwards
for (int row = n - 2; row >= 0; --row) {
for (int col = 0; col < triangle[row].size(); ++col) {
// Update the current value to the minimum path sum
triangle[row][col] += min(triangle[row + 1][col], triangle[row + 1][col + 1]);
}
}
// The top element now contains the minimum path sum
return triangle[0][0];
}
};
11.07MB, 4ms
Javascript
/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
// Start from the second last row and move upwards
for (let row = triangle.length - 2; row >= 0; row--) {
for (let col = 0; col < triangle[row].length; col++) {
// Update the current value to the minimum path sum
triangle[row][col] += Math.min(triangle[row + 1][col], triangle[row + 1][col + 1]);
}
}
// The top element now contains the minimum path sum
return triangle[0][0];
};
49.26MB, 62ms
