DSA - Triangle - C++,Dynamic Programming

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:

1. The solve function is a recursive helper function that calculates the minimum path sum from a given position (row, col) in the triangle grid.

2. 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.

3. 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.

4. 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.

5. 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.

6. The minimumTotal function initializes a 2D dynamic programming table dp of the same size as the triangle grid, with all values set to -1.

7. 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.

8. 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