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 eitherm
orn
is negative (out of bounds), it returnsINT_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 tabledp
. 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 variableup
.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 variableleft
.
Returning the minimum path sum:
The function calculates the minimum path sum for the current cell
(m, n)
as the minimum betweenup
andleft
, then adds the value of the current cellgrid[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
andn
of the grid.It creates a memoization table
dp
with dimensionsm 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 dimensionsm = 3
andn = 3
and creates the memoization tabledp
:
cssCopy codedp = [ [-1, -1, -1],
[-1, -1, -1],
[-1, -1, -1]
]
The
solve
function is called withm = 2
,n = 2
, and the grid anddp
table as arguments.In the
solve
function:The base case is not triggered since
m
andn
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)
returns1 + 3 = 4
.left = solve(1, 0, grid, dp)
returns1 + 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 thedp
table:
cssCopy codedp = [ [-1, -1, 4],
[-1, 7, -1],
[6, -1, -1]
]
- The final result is returned from the
minPathSum
function asdp[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.