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)

Finally, the answer is dp[m-1][n-1].

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) {
  // your code here
}

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];
    }
}