## Table of contents

### No headings in the article.

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:

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

.

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.

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)`

.

- 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]
]
```

The

`solve`

function is called with`m = 2`

,`n = 2`

, and the grid and`dp`

table as arguments.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)`

.

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)`

.

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`

.

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`

.

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`

.

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]
]
```

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