Given a triangle
array, return the minimum path sum from top to bottom.
For each step, you may move to an adjacent number of the row below. More formally, if you are on index i
on the current row, you may move to either index i
or index i + 1
on the next row.
Example 1:
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] Output: 11 Explanation: The triangle looks like: 2 3 4 6 5 7 4 1 8 3 The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).
Example 2:
Input: triangle = [[-10]] Output: -10
Constraints:
1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104
Follow up: Could you do this using only
O(n)
extra space, where n
is the total number of rows in the triangle?Given a triangle array, find the minimum path sum from top to bottom. At each step, you can move to an adjacent number in the row below.
This problem can be efficiently solved using dynamic programming. The core idea is to build a solution from the bottom up.
Approach:
Initialization: We can either create a separate DP table or, for space optimization, directly modify the input triangle
array. The approach using the input array is shown below, offering O(1) space complexity.
Iteration: We iterate through the triangle from the second to last row upwards. For each element triangle[i][j]
, we add the minimum of its two adjacent elements in the row below (triangle[i+1][j]
and triangle[i+1][j+1]
). This represents the minimum path sum from that element to the bottom of the triangle.
Result: After iterating through all rows, triangle[0][0]
will contain the minimum total path sum from the top to the bottom.
Time and Space Complexity:
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
for i in range(n - 2, -1, -1):
for j in range(i + 1):
triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])
return triangle[0][0]
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
for (int i = triangle.size() - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i + 1).get(j), triangle.get(i + 1).get(j + 1)));
}
}
return triangle.get(0).get(0);
}
}
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
for (int i = triangle.size() - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]);
}
}
return triangle[0][0];
}
};
/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
for (let i = triangle.length - 2; i >= 0; i--) {
for (let j = 0; j <= i; j++) {
triangle[i][j] += Math.min(triangle[i + 1][j], triangle[i + 1][j + 1]);
}
}
return triangle[0][0];
};
func minimumTotal(triangle [][]int) int {
for i := len(triangle) - 2; i >= 0; i-- {
for j := 0; j <= i; j++ {
triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1])
}
}
return triangle[0][0]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
These solutions all follow the same dynamic programming approach, differing only in syntax. The in-place modification optimizes space complexity, making them highly efficient.