Last Updated: 6 Nov, 2020
Min Cost Path
Moderate
Asked in companies
You have been given a matrix of ‘N’ rows and ‘M’ columns filled up with integers. Find the minimum sum that can be obtained from a path which starts from the top left corner and ends with the bottom right corner.
From any cell in a row, we can move to the right, down or the down-right diagonal cell. So from a particular cell (row, col), we can move to the following three cells:
Down: (row+1,col)
Right: (row, col+1)
Down right diagonal: (row+1, col+1)
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain two integers ‘N’ and ‘M’ denoting the number of rows and columns, respectively.
Next ‘N’ lines contain ‘M’ space-separated integers each denoting the elements in the matrix.
Output Format:
For each test case, print an integer which represents the minimum sum that can be obtained by travelling a path as described above.
Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of.
Constraints:
1 <= T <= 50
1 <= N, M <= 100
-10000 <= cost[i][j] <= 10000
Where ‘T’ is the number of test cases.
Where 'N' is the number of rows in the given matrix, and 'M' is the number of columns in the given matrix.
And, cost[i][j] denotes the value at (i,j) cell in the matrix.
Time limit: 1 sec
Approaches
The basic idea is to explore all possible paths recursively and return the minimum path sum among them. Steps are as follows:
- Start exploring the path from the top left corner (0, 0).
- Let us assume that we are currently at (row, col)th cell. If this cell is outside the boundary of the matrix, then return infinite(a very large number) because we don’t want to include the current cell into our path.
- If the current cell is (N-1, M-1)th cell then return the value of the current cell. Else for the rest of the cells,
- There are three options possible for the next move
- (row, col+1)th cell
- (row+1, col)th cell
- (row+1, col+1)th cell
- Break the primary problem into three subproblems which are finding minimum path sum from the cells mentioned above.
- Now, among the above three paths, find the path which has the minimum sum. And whatever solution we will get from the above three problems. We will take a minimum of them and the sum of cost[row][col], which will be the minimum path cost to reach (N-1, M-1) from (row, col).
- Repeat the whole process recursively.
The approach mentioned above can be formalised in the following manner.
Let minPathSum(row, col) is a function which returns the minimum path sum which can be obtained while moving from (row, col) to (N-1, M-1).
minPathSum(row, col) = min( minPathSum(row+1, col), minPathSum(row, col+1), minPathSum(row+1, col+1) ) + cost[row][col] Let us try to analyse the recursive tree from the previous approach when ‘N’ = 3 and ‘M’ = 3.
After observing the tree, we’ll find that there are some redundant function calls which mean that there are some overlapping subproblems. The repetition of such sub-problems suggests that we can use dynamic programming to optimise our approach.
The key idea behind a dynamic programming approach is to use memoization, i.e. we’ll save the result of our sub-problem in a matrix so that it can be used later on.
Let dp[row][col] be our dynamic programming matrix to store the minimum path sum which starts from (row, col)th cell and ends at (N-1, M-1)th cell. It will help us to avoid redundant function calls. Steps are as follows:
- Before calling the function for any valid (row, col), we will first check whether we have already a solution corresponding to the (row, col), if we have already a solution then we return the solution else we will solve it with following steps :
- If the current cell is (N-1, M-1)th cell then return the value of the current cell. And for the rest of the cells,
- We can move to follow three cells from the cell (row, col)
- Down move : (row+1, col)
- Right move: (row, col+1)
- Downright diagonal move : (row+1, col+1)
- Now among the above three paths, the path having the minimum sum will be the minimum path sum from (row, col). So return the sum of the current cell and minimum path sum such which we got from the above three paths.
- Store the answer in the “dp” table for later use.
The key idea behind this approach is to update the given cost[][] matrix itself instead of using a “dp” matrix.
We will iterate through each row of the cost[][] matrix and will update the value of the (row, col)th element with the minimum path sum from (0, 0) to (row, col).
- Let us assume that we are currently at (row, col)th element; we must have arrived here from either of the following cells:
- from the top cell (row-1, col)
- from the left cell (row, col-1)
- from the up-left diagonal cell (row-1, col-1)
- Discard those options which are outside the boundary of our matrix.
- The minimum path sum from (0, 0) to (row, col) will be the summation of cost[row][col] and the minimum value among the cells mentioned above.
i.e. cost[row][col] = min(cost[row-1][col], cost[row][col-1] , cost[row-1][col-1]) + cost[row][col]4. If the current cell is the bottom right corner (N-1, M-1), we’ll stop our iterative process.
Since, cost[row-1][col-1] now represents the minimum path sum from (0, 0) to (row-1, col-1), cost[N-1][M-1] will be our answer.