# Solution For Minimum Path Cost In A Grid

Problem statement

Given a m x n grid containing non-negative integers, find the minimum sum path from top left to bottom right corner.

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

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

Example 2:
Input: grid = [[1,2,3],[4,5,6]] Output: 12

Solution:

We can solve this problem by using dynamic programming. We can create a 2D table dp[][] to store the minimum path sum from grid[0][0] to grid[i][j]. dp[i][j] can be computed as:

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

The base cases are:

1. dp[0][0] = grid[0][0]
2. For i = 1 to m-1, dp[i][0] = dp[i-1][0] + grid[i][0] (since we can only move down from top-left corner)
3. For j = 1 to n-1, dp[0][j] = dp[0][j-1] + grid[0][j] (since we can only move right from top-left corner)

Code:

class Solution {
public:
int minPathSum(vector>& grid) {
int m = grid.size();
int n = grid[0].size();
vector>dp(m,vector(n));

``````    dp[0][0] = grid[0][0];

for(int i=1;i<m;i++){
dp[i][0] = dp[i-1][0] + grid[i][0];
}

for(int j=1;j<n;j++){
dp[0][j] = dp[0][j-1] + grid[0][j];
}

for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]);
}
}

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

};

Time Complexity : O(m x n)
Space Complexity : O(m x n)

## Step by Step Implementation For Minimum Path Cost In A Grid

```The problem is as follows:

Given a grid of size m x n, each cell of the grid contains a positive integer representing the cost of traversing that cell. The cost of a path is the sum of the costs of the cells in that path. Find the minimum cost of a path from the top left cell of the grid to the bottom right cell.

Here is a Java solution:

public int minPathCost(int[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < n; i++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
for (int j = 1; j < m; j++) {
dp[j][0] = dp[j - 1][0] + grid[j][0];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}```
```def minPathSum(grid):
# base case: if the grid is empty, return 0
if not grid:
return 0

# get the number of rows and columns in the grid
num_rows, num_cols = len(grid), len(grid[0])

# create a 2D array to store the minimum path sum for each cell in the grid
min_path_sums = [[0 for _ in range(num_cols)] for _ in range(num_rows)]

# initialize the first row and column of the minimum path sums array
min_path_sums[0][0] = grid[0][0]

# fill in the first row of the minimum path sums array
for col in range(1, num_cols):
min_path_sums[0][col] = grid[0][col] + min_path_sums[0][col-1]

# fill in the first column of the minimum path sums array
for row in range(1, num_rows):
min_path_sums[row][0] = grid[row][0] + min_path_sums[row-1][0]

# fill in the rest of the minimum path sums array
for row in range(1, num_rows):
for col in range(1, num_cols):
min_path_sums[row][col] = grid[row][col] + min(min_path_sums[row-1][col], min_path_sums[row][col-1])

# return the value in the bottom right corner of the minimum path sums array
return min_path_sums[-1][-1]```
```// Minimum Path Cost in a Grid

// Given a grid where each cell represents the cost to travel to that cell, find the minimum cost to travel from the top left cell to the bottom right cell. You can only travel down or right.

// For example, given the following grid:

// [
//   [1, 3, 1],
//   [1, 5, 1],
//   [4, 2, 1]
// ]
// The minimum cost to get from the top left to the bottom right is 7 (1 + 3 + 1 + 1 + 2 + 1 = 7).

function minPathCost(grid) {
}```
```The problem is as follows:

Given a grid of size m x n, each cell in the grid has a value. The value of each cell represents the cost of that cell, and you can only move from one cell to another if the cost of the destination cell is lower than the cost of the current cell. Find the minimum cost to move from the top-left cell to the bottom-right cell of the grid.

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

The solution is as follows:

/*

We can solve this problem using dynamic programming. We create a 2D array dp of size m x n, where dp[i][j] represents the minimum cost to reach cell (i,j) from the top-left cell (0,0). We initialize dp[0][0] = grid[0][0].

Then, we fill in the rest of the entries in the dp array, starting from the top-left cell and moving right and down. For each cell (i,j), we compute dp[i][j] as the minimum of dp[i-1][j] (the cost to reach the cell to the left of (i,j)) and dp[i][j-1] (the cost to reach the cell above (i,j)), plus the cost of the current cell, grid[i][j].

The final answer is dp[m-1][n-1], the minimum cost to reach the bottom-right cell of the grid.

*/

#include

using namespace std;

int main() {

int m, n;

cin >> m >> n;

vector> grid(m, vector(n));

for (int i = 0; i < m; i++) {

for (int j = 0; j < n; j++) {

cin >> grid[i][j];

}

}

vector> dp(m, vector(n));

dp[0][0] = grid[0][0];

for (int i = 1; i < m; i++) {

dp[i][0] = dp[i-1][0] + grid[i][0];

}

for (int j = 1; j < n; j++) {

dp[0][j] = dp[0][j-1] + grid[0][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];

}

}

cout << dp[m-1][n-1] << endl;

return 0;

}```
```using System;

public class Solution {
public int MinPathSum(int[][] grid) {
int m = grid.Length;
int n = grid[0].Length;

// Create a 2D array to store the minimum path sum
int[,] dp = new int[m,n];

// Fill in the first row and column of the 2D array
for(int i = 0; i < m; i++)
{
dp[i,0] = grid[i][0] + (i > 0 ? dp[i-1,0] : 0);
}

for(int j = 0; j < n; j++)
{
dp[0,j] = grid[0][j] + (j > 0 ? dp[0,j-1] : 0);
}

// Fill in the rest of the 2D array
for(int i = 1; i < m; i++)
{
for(int j = 1; j < n; j++)
{
dp[i,j] = grid[i][j] + Math.Min(dp[i-1,j], dp[i,j-1]);
}
}

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

## Top 100 Leetcode Practice Problems In Java

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