# Solution For Minimum Path Sum

Problem statement:

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
[1,3,1],
[1,5,1],
[4,2,1] ] Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Solution:

To solve this problem, we can use dynamic programming. We can create a 2D matrix of the same size as the input matrix and fill it with the minimum sum required to reach each cell.

Let us assume that, the top-left corner of the input matrix is (0, 0) and the bottom-right corner is (m – 1, n – 1). For the first row and first column, we can directly copy the value from the input matrix because there is only one way to reach each cell in these rows and columns i.e., moving right in the first row and moving down in the first column.

For the rest of the matrix, we can determine the minimum sum required to reach each cell by taking the minimum value from the previous cells in the same row and column and adding the current cell value. We can express this idea using the following recurrence relation:

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

where dp[i][j] represents the minimum sum required to reach cell (i, j) in the input matrix, and grid[i][j] represents the cell value in the input matrix.

After filling the dp matrix, the minimum sum required to reach the bottom-right corner will be present in dp[m-1][n-1]. So, we return that value as the answer.

Here is the Python code to implement the above approach:

def minPathSum(grid):
m, n = len(grid), len(grid)
dp = [[0 for _ in range(n)] for _ in range(m)]

``````# initialize the first row
dp = grid
for j in range(1, n):
dp[j] = dp[j-1] + grid[j]

# initialize the first column
for i in range(1, m):
dp[i] = dp[i-1] + grid[i]

# fill the rest of the matrix
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

return dp[m-1][n-1]
``````

Time complexity: O(m*n), where m and n are the dimensions of the input matrix.

Space complexity: O(mn), since we are using a 2D matrix of size mn to store the intermediate results.

## Step by Step Implementation For Minimum Path Sum

```class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid.length;
int[][] dp = new int[m][n];
dp = grid;
for(int i=1;iGiven a m x n grid filled with non-negative numbers, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following grid:

[
[1,3,1],
[1,5,1],
[4,2,1]
]
The minimum path sum from top to bottom is 7, which is 1 + 3 + 1 + 1 + 1 + 2 + 1 = 7.

Note: You can only move either down or right at any point in time.

def minPathSum(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
if not grid:
return
r = len(grid)
c = len(grid)
dp = [[0 for x in range(c)] for x in range(r)]
dp = grid

# Fill the first row and first column separately
# because we need to consider only left column and
# top row while filling the first row and column
for i in range(1, r):
dp[i] = dp[i-1] + grid[i]

for j in range(1, c):
dp[j] = dp[j-1] + grid[j]

# fill the dp table in bottom-up fashion
for i in range(1, r):
for j in range(1, c):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

return dp[-1][-1]/**
* @param {number[][]} grid
* @return {number}
*/

// DP solution
var minPathSum = function(grid) {
// create a 2D array to store the min path sum up to each point
let minGrid = [];
for (let i = 0; i < grid.length; i++) {
minGrid.push(new Array(grid.length).fill(0));
}

// fill in the first row and column
for (let i = 0; i < grid.length; i++) {
minGrid[i] = grid[i] + (i > 0 ? minGrid[i-1] : 0);
}
for (let j = 0; j < grid.length; j++) {
minGrid[j] = grid[j] + (j > 0 ? minGrid[j-1] : 0);
}

// fill in the rest of the table
for (let i = 1; i < grid.length; i++) {
for (let j = 1; j < grid.length; j++) {
minGrid[i][j] = grid[i][j] + Math.min(minGrid[i-1][j], minGrid[i][j-1]);
}
}

return minGrid[grid.length-1][grid.length-1];
};int minPathSum(vector>& grid) {
int m = grid.size();
int n = grid.size();
vector> dp(m, vector(n, 0));
dp = grid;
for(int i = 1; i < m; i++) {
dp[i] = dp[i-1] + grid[i];
}
for(int j = 1; j < n; j++) {
dp[j] = dp[j-1] + grid[j];
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}using System;

namespace Minimum_Path_Sum
{
class Program
{
static void Main(string[] args)
{
int[,] grid = new int[,] { { 1, 3, 1 },
{ 1, 5, 1 },
{ 4, 2, 1 } };
Console.WriteLine(MinPathSum(grid));
}

// Function to find the minimum path sum
static int MinPathSum(int[,] grid)
{
int rows = grid.GetLength(0);
int cols = grid.GetLength(1);

// Declare a 2D array to store the sum of
// minimum path
int[,] dp = new int[rows, cols];

// Fill the first column of the array
for (int i = 0; i < rows; i++)
dp[i, 0] = grid[i, 0] +
(i > 0 ? dp[i - 1, 0] : 0);

// Fill the first row of the array
for (int j = 1; j < cols; j++)
dp[0, j] = grid[0, j] +
(j > 0 ? dp[0, j - 1] : 0);

// Fill rest of the array
for (int i = 1; i < rows; i++)
{
for (int j = 1; j < cols; j++)
{
// If i == 0 or j == 0, then we can
// only move in one direction
if (i == 0)
dp[i, j] = grid[i, j] + dp[i, j - 1];
else if (j == 0)
dp[i, j] = grid[i, j] + dp[i - 1, j];

// Otherwise, we take the minimum of the
// top and left elements
else
dp[i, j] = grid[i, j] +
Math.Min(dp[i - 1, j],
dp[i, j - 1]);
}
}

// Return the minimum path sum
return dp[rows - 1, cols - 1];
}
}
}```
Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]