## 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 the`dp`

table (`dp[row][col] != -1`

), the function directly returns that value from the`dp`

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 variables`down`

and`downRight`

.Finally, the function calculates the minimum path sum for the current position by taking the minimum of

`down`

and`downRight`

and adding the value of the current cell`triangle[row][col]`

. It assigns this value to`dp[row][col]`

and returns it.The

`minimumTotal`

function initializes a 2D dynamic programming table`dp`

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