Table of contents
No headings in the article.
Hey, so today we are going to solve Leetcode - Triangle
Problem Link- https://leetcode.com/problems/triangle/
class Solution {
public:
int solve(vector<vector<int>>& triangle, vector<vector<int>>& dp, int row, int col){
if(row == triangle.size() - 1) {
return triangle[row][col];
}
if(dp[row][col] != -1) {
return dp[row][col];
}
int down = INT_MAX;
int downRight = INT_MAX;
int down = solve(triangle, dp, row+1, col);
int downRight = solve(triangle, dp, row+1, col+1);
return dp[row, col] = min(down, downRight) + triangle[row][col];
}
int minimumTotal(vector<vector<int>>& triangle) {
vector<vector<int>> dp(triangle.size(), vector<int>(triangle.size(), -1));
return solve(triangle, dp, 0, 0);
}
}
Here's a step-by-step explanation of the code and its visualization:
The
solve
function is a recursive helper function that calculates the minimum path sum from a given position(row, col)
in the triangle grid.The function checks if the current position
(row, col)
is at the last row of the triangle (row == triangle.size() - 1
). If so, it means we have reached the bottom of the triangle, and it returns the value of that cell, which represents the minimum path sum at that position.If the minimum path sum for the current position
(row, col)
has already been calculated and stored in thedp
table (dp[row][col] != -1
), the function directly returns that value from thedp
table. This is known as memoization, which avoids redundant calculations and improves performance.If the above conditions are not met, the function recursively calculates the minimum path sums for the cells below the current position. It calls the
solve
function for the positions(row + 1, col)
and(row + 1, col + 1)
, representing the cell directly below and to the right of the current position, respectively. It stores the results in the variablesdown
anddownRight
.Finally, the function calculates the minimum path sum for the current position by taking the minimum of
down
anddownRight
and adding the value of the current celltriangle[row][col]
. It assigns this value todp[row][col]
and returns it.The
minimumTotal
function initializes a 2D dynamic programming tabledp
of the same size as the triangle grid, with all values set to -1.It calls the
solve
function with the initial position(0, 0)
to calculate the minimum path sum from the top of the triangle to the bottom, considering all possible paths.The function returns the minimum path sum stored in
dp[0][0]
, which represents the minimum path sum for the entire triangle.
In summary, the code uses dynamic programming with memoization to efficiently calculate the minimum path sum in a triangle-shaped grid. It breaks down the problem into smaller subproblems and reuses previously calculated solutions to avoid redundant calculations. This approach improves performance