DSA - Minimum Path Sum - C++,Dynamic Programming

Hey, so today we are going to solve Leetcode - Minimum Path Sum

Problem Link- https://leetcode.com/problems/minimum-path-sum/

class Solution {
public:
    int solve(int m, int n, vector<vector<int>>& grid, vector<vector<int>>& dp){
      if(m<0 || n < 0) return INT_MAX;

      if(dp[m][n] != -1) return dp[m][n];

      int up = solve(m-1, n , grid, dp); 
      int left = solve(m, n-1, grid, dp); 

      return dp[m][n] = min(up, left) + grid[m][n];
    }

    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(); int n = grid[0].size(); 
        vector<vector<int>> dp(m, vector<int>(n, -1));

        return solve(m-1, n-1, grid, dp);
    }
};

The code defines a Solution class that encapsulates the logic for finding the minimum path sum in a grid. The key method is minPathSum, which calculates the minimum path sum using the solve recursive helper function.

The solve function takes the current row m, current column n, the grid matrix, and the memoization table dp as parameters. It returns the minimum path sum from the top-left cell to the current cell (m, n).

Here's a step-by-step explanation of the code and its visualization:

1. The solve function checks the base case: if either m or n is negative (out of bounds), it returns INT_MAX. This is to prevent considering invalid cells during the recursive calls.

2. The memoization step: The function checks if the result for the current cell (m, n) is already stored in the memoization table dp. If so, it returns the stored result directly. This avoids redundant calculations for cells that have already been visited.

3. Recursive calls:

   • The function recursively calls itself to find the minimum path sum for the cell above (m-1, n) and stores it in the variable up.

   • It also recursively calls itself to find the minimum path sum for the cell to the left (m, n-1) and stores it in the variable left.

4. Returning the minimum path sum:

   • The function calculates the minimum path sum for the current cell (m, n) as the minimum between up and left, then adds the value of the current cell grid[m][n].

   • The result is stored in the memoization table dp[m][n] to avoid redundant calculations in future recursive calls.

5. The minPathSum function:

   • It initializes the dimensions m and n of the grid.

   • It creates a memoization table dp with dimensions m x n, initializing all values to -1.

   • It calls the solve function, passing the starting cell (m-1, n-1), the grid, and the memoization table as arguments.

   • It returns the result, which represents the minimum path sum from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1).

Visually, the code solves the minimum path sum problem by recursively exploring all possible paths from the top-left to the bottom-right cell. It uses memoization to store the results of already calculated subproblems, which significantly reduces redundant calculations and improves the efficiency of the solution.

Note that the code assumes that the grid is a valid input, meaning it is non-empty and all rows and columns have at least one element. It also assumes that the grid elements are non-negative.

To visualize the process, let's consider a simple example with the following grid:

cssCopy codegrid = [  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
]

We start with the top-left cell (0, 0) and want to find the minimum path sum to reach the bottom-right cell (2, 2).

1. The minPathSum function initializes the dimensions m = 3 and n = 3 and creates the memoization table dp:

cssCopy codedp = [  [-1, -1, -1],
  [-1, -1, -1],
  [-1, -1, -1]
]

1. The solve function is called with m = 2, n = 2, and the grid and dp table as arguments.

2. In the solve function:

   • The base case is not triggered since m and n are not negative.

   • The memoization check is performed, and since dp[2][2] is -1, we proceed with the calculations.

   • Recursive calls are made:

     • up = solve(1, 2, grid, dp): This explores the path from (1, 2) to (2, 2).

     • left = solve(2, 1, grid, dp): This explores the path from (2, 1) to (2, 2).

3. Recursive calls continue until we reach cells (0, 2) and (2, 0):

   • up = solve(0, 2, grid, dp): This explores the path from (0, 2) to (1, 2).

   • left = solve(1, 1, grid, dp): This explores the path from (1, 1) to (2, 1).

   • up = solve(1, 1, grid, dp): This explores the path from (1, 1) to (1, 2).

   • left = solve(2, 0, grid, dp): This explores the path from (2, 0) to (2, 1).

4. The base case is triggered when we reach the cells (0, 1) and (1, 0) (top row and leftmost column):

   • up = solve(0, 1, grid, dp) returns 1 + 3 = 4.

   • left = solve(1, 0, grid, dp) returns 1 + 1 = 2.

5. The minimum path sum for cells (0, 2) and (2, 0) is calculated:

   • dp[0][2] = min(up, left) + grid[0][2] = min(4, 2) + 1 = 3 + 1 = 4.

   • dp[2][0] = min(up, left) + grid[2][0] = min(4, 2) + 4 = 2 + 4 = 6.

6. The minimum path sum for cell (1, 1) is calculated:

   • dp[1][1] = min(up, left) + grid[1][1] = min(4, 2) + 5 = 2 + 5 = 7.

7. The minimum path sum for cells (0, 2) and (2, 0) as well as cell (1, 1) is stored in the dp table:

cssCopy codedp = [  [-1, -1, 4],
  [-1, 7, -1],
  [6, -1, -1]
]

1. The final result is returned from the minPathSum function as dp[2][2], which is 7.

This means that the minimum path sum from the top-left cell (0, 0) to the bottom-right cell (2, 2) in the given grid is 7.

By using the recursive approach with memoization, the code avoids redundant calculations and computes the minimum path sum efficiently. The memoization table dp stores the results of previously calculated subproblems, allowing for quick lookup and reusability. This improves the overall time complexity of the solution.

It's important to note that the code assumes the grid contains valid values and that there is at least one valid path from the top-left cell to the bottom-right cell. If there are obstacles or invalid cells, modifications to the code may be required to handle such cases appropriately.