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[0])
dp = [[0 for _ in range(n)] for _ in range(m)]

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

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

# 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[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for(int i=1;i
Given 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[0])
        dp = [[0 for x in range(c)] for x in range(r)] 
        dp[0][0] = grid[0][0]
        
        # 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][0] = dp[i-1][0] + grid[i][0] 
              
        for j in range(1, c): 
            dp[0][j] = dp[0][j-1] + grid[0][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[0].length).fill(0));
    }
    
    // fill in the first row and column
    for (let i = 0; i < grid.length; i++) {
        minGrid[i][0] = grid[i][0] + (i > 0 ? minGrid[i-1][0] : 0);
    }
    for (let j = 0; j < grid[0].length; j++) {
        minGrid[0][j] = grid[0][j] + (j > 0 ? minGrid[0][j-1] : 0);
    }
    
    // fill in the rest of the table
    for (let i = 1; i < grid.length; i++) {
        for (let j = 1; j < grid[0].length; j++) {
            minGrid[i][j] = grid[i][j] + Math.min(minGrid[i-1][j], minGrid[i][j-1]);
        }
    }
    
    return minGrid[grid.length-1][grid[0].length-1];
};
int minPathSum(vector>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector> dp(m, vector(n, 0));
        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];
            }
        }
        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]; 
        } 
    } 
}