Description:
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.
Examples:
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: -10Solution in Python:
To solve the problem of finding the minimum path sum from the top to the bottom of a triangle, we can use dynamic programming. The idea is to start from the bottom of the triangle and work our way upwards, updating the path sums in place. This approach allows us to use only O(n) extra space, where n is the number of rows in the triangle.
from typing import List
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
if not triangle:
return 0
# Start from the second last row and move upwards to the top
for row in range(len(triangle) - 2, -1, -1):
for col in range(len(triangle[row])):
# Update the current cell with the sum of the cell and the minimum of the two adjacent cells in the row below
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]The dynamic programming approach works by modifying the triangle in place, starting from the bottom row and moving upwards. At each cell, we add the minimum of the possible paths from the row below, ensuring that we accumulate the minimum path sum as we move to the top. This approach effectively reduces the problem size step by step, and by the time we reach the top, we have computed the minimum path sum. This in-place modification allows us to solve the problem using O(n) extra space, as required.
Solution in Javascript:
/**
* @param {number[][]} triangle
* @return {number}
*/
var minimumTotal = function(triangle) {
// If the triangle is empty, return 0
if (triangle.length === 0) {
return 0;
}
// Start from the second last row and move upwards to the top
for (let row = triangle.length - 2; row >= 0; row--) {
for (let col = 0; col < triangle[row].length; col++) {
// Update the current cell with the sum of the cell and the minimum of the two adjacent cells in the row below
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];
};Solution in Java:
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
// If the triangle is empty, return 0
if (triangle == null || triangle.size() == 0) {
return 0;
}
// Start from the second last row and move upwards to the top
for (int row = triangle.size() - 2; row >= 0; row--) {
// Iterate through each element in the current row
for (int col = 0; col < triangle.get(row).size(); col++) {
// Update the current cell with the sum of the cell and the minimum of the two adjacent cells in the row below
int currentVal = triangle.get(row).get(col);
int below = triangle.get(row + 1).get(col);
int belowRight = triangle.get(row + 1).get(col + 1);
int minPathSum = currentVal + Math.min(below, belowRight);
triangle.get(row).set(col, minPathSum);
}
}
// The top element now contains the minimum path sum
return triangle.get(0).get(0);
}
}Solution in C#:
public class Solution {
public int MinimumTotal(IList<IList<int>> triangle) {
// If the triangle is empty, return 0
if (triangle == null || triangle.Count == 0) {
return 0;
}
// Start from the second last row and move upwards to the top
for (int row = triangle.Count - 2; row >= 0; row--) {
// Iterate through each element in the current row
for (int col = 0; col < triangle[row].Count; col++) {
// Update the current cell with the sum of the cell and the minimum of the two adjacent cells in the row below
int currentVal = triangle[row][col];
int below = triangle[row + 1][col];
int belowRight = triangle[row + 1][col + 1];
int minPathSum = currentVal + Math.Min(below, belowRight);
triangle[row][col] = minPathSum;
}
}
// The top element now contains the minimum path sum
return triangle[0][0];
}
}