Minimum path sum (DP-14)

You are given an m x n matrix filled with non-negative integers, you need to find a path from top left to bottom right of the matrix with minimum sum of the numbers along the path. You can only move only down or right at any point of time.

Sample Input:

[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]

Expected Output: 7
Explanation: The path 1-3-1-1-1 is the resulting path with minimum sum 7.

Algorithm:

The problem can be solved using dynamic programming since it has both optimal substructure and overlapping sub-problems.

  1. We create a 2D array DP with the same size as that of the grid. DP [i][j] will store the result for the minimum path sum from top left to cell at i’th row and j’th column.
  2. We initialize first cell of DP with the first cell of the given matrix. For all other cells in the first row as well as in the first column, we initialize them with the sum of previous cell of that row or column and the current cell in the given matrix.
  3. For all other cells, we iterate and in each iteration, we do the following.
    We set DP [i][j] equal to the sum of current element and the minimum of DP [i-1][j] and DP [i][j-1] because we are only allowed to move bottom or right.
#include <bits/stdc++.h>
using namespace std;
int minPathSum(vector<vector<int>>& grid) {
    int r = grid.size();
    int c = grid[0].size();
    vector<vector<int>> lookup(r, vector<int>(c));
    lookup[0][0] = grid[0][0];
    for(int i=1; i<r; i++){
        lookup[i][0] = lookup[i-1][0] + grid[i][0];
    }
    for(int i=1; i<c; i++){
        lookup[0][i] = lookup[0][i-1] + grid[0][i];
    }
    for(int i=1; i<r; i++){
        for(int j=1; j<c; j++){
            lookup[i][j] = grid[i][j] + min(lookup[i-1][j], lookup[i][j-1]);
        }
    }
    return lookup[r-1][c-1];
}
 int main(){
 	vector<vector<int>> input = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
 	cout<<minPathSum(input);
 	return 0;
 }

Also, check out another popular interview problem Maximum Size Square Sub-matrix.

4 comments

  1. Have a cool suggestion. It would he really great if you allow a service like, improve article. The contributions will be more on the website. Also different versions of languages and approaches will be there, so it will boost the growth.

Leave a Reply

Your email address will not be published.