Dare2Solve
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.
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.
Initialization:
n
of the triangle
.dp
of size n x n
initialized with a large value (float('inf')
in Python).Recursive Function with Memoization:
f(i, j)
that returns the minimum path sum starting at triangle[i][j]
.i
is the last row, return the value at triangle[i][j]
.dp[i][j]
is not float('inf')
, return the stored value to avoid redundant calculations.dp[i][j]
.Return the Result:
f(0, 0)
) and return the result.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.
O(n^2), which is the space required for the 2D dp array to store the minimum path sums for each element.
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
function<int(int, int)> 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);
}
};
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)
class Solution {
public int minimumTotal(List<List<Integer>> 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<List<Integer>> 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<List<Integer>> 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
}
}
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);
};