🎨Now live: Try our Free AI Image Generation Feature

Description
Given a triangle array, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
Intuition
The problem can be broken down into simpler subproblems, making it a good candidate for dynamic programming. By starting from the bottom of the triangle and working upwards, we can calculate the minimum path sum for each element, ultimately finding the minimum path sum from the top of the triangle.
Approach
- Initialization:
- Determine the size
n
of thetriangle
. - Create a 2D listdp
of sizen x n
initialized with a large value (float('inf')
in Python). - Recursive Function with Memoization:
- Define a helper function
f(i, j)
that returns the minimum path sum starting attriangle[i][j]
. - Base Case: Ifi
is the last row, return the value attriangle[i][j]
. - Memoization: Ifdp[i][j]
is notfloat('inf')
, return the stored value to avoid redundant calculations. - Compute the minimum path sum for the current position by considering both the path going directly down and the path going diagonally down-right. - Store the computed minimum path sum indp[i][j]
. - Return the Result:
- Call the helper function starting from the top of the triangle (
f(0, 0)
) and return the result.
Complexity
Time Complexity:
O(n^2), where n is the number of rows in the triangle. This is because each element in the triangle is processed once, and each recursive call is memoized.
Space Complexity:
O(n^2), which is the space required for the 2D dp array to store the minimum path sums for each element.
Code
C++
class Solution {
public:
int minimumTotal(vector>& triangle) {
int n = triangle.size();
vector> dp(n, vector(n, INT_MAX));
function f = [&](int i, int j) -> int {
if (i == n - 1) {
return triangle[i][j];
}
if (dp[i][j] != INT_MAX) {
return dp[i][j];
}
int down = triangle[i][j] + f(i + 1, j);
int diag = triangle[i][j] + f(i + 1, j + 1);
return dp[i][j] = min(down, diag);
};
return f(0, 0);
}
};
Python
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
dp = [[float('inf')] * n for _ in range(n)]
def f(i: int, j: int) -> int:
if i == n - 1:
return triangle[i][j]
if dp[i][j] != float('inf'):
return dp[i][j]
down = triangle[i][j] + f(i + 1, j)
diag = triangle[i][j] + f(i + 1, j + 1)
dp[i][j] = min(down, diag)
return dp[i][j]
return f(0, 0)
Java
class Solution {
public int minimumTotal(List> triangle) {
int n = triangle.size();
int[][] dp = new int[n][n];
// Initialize the dp array with a large value
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = Integer.MAX_VALUE;
}
}
// Recursive function with memoization
return f(triangle, 0, 0, dp);
}
private int f(List> triangle, int i, int j, int[][] dp) {
int n = triangle.size();
if (i == n - 1) {
return triangle.get(i).get(j);
}
if (dp[i][j] != Integer.MAX_VALUE) {
return dp[i][j];
}
int down = triangle.get(i).get(j) + f(triangle, i + 1, j, dp);
int diag = triangle.get(i).get(j) + f(triangle, i + 1, j + 1, dp);
dp[i][j] = Math.min(down, diag);
return dp[i][j];
}
public static void main(String[] args) {
Solution solution = new Solution();
List> triangle = new ArrayList<>();
triangle.add(List.of(2));
triangle.add(List.of(3, 4));
triangle.add(List.of(6, 5, 7));
triangle.add(List.of(4, 1, 8, 3));
System.out.println(solution.minimumTotal(triangle)); // Output: 11
}
}
JavaScript
var minimumTotal = function(triangle) {
let n = triangle.length;
let dp = Array(n).fill(Number.MAX_VALUE).map(()=> Array(n).fill(Number.MAX_VALUE));
//let min = Number.MAX_VALUE;
function f(i, j){
if(i == n-1){return triangle[i][j];}
if(dp[i][j] != Number.MAX_VALUE) return dp[i][j];
let down = triangle[i][j] + f(i+1, j);
let diag = triangle[i][j] + f(i+1, j+1);
return dp[i][j] = Math.min(down, diag);
}
return f(0, 0);
};