Minimum Cost Path
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 from cell (x,y) and ends at the top left corner (1,1).

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 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. The last line will contain two integers ‘x’ and ‘y’ denoting the cell to start from.

Output Format:

For each test case, print an integer that represents the minimum sum that can be obtained by traveling 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

Question

Minimum Cost Path

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 from cell (x,y) and ends at the top left corner (1,1).

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 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.

The last line will contain two integers ‘x’ and ‘y’ denoting the cell to start from.

Output Format:

For each test case, print an integer that represents the minimum sum that can be obtained by traveling 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
1 <= x, y <= 100

Time limit: 1 sec

Accepted Answer

Recursive Approach

Let’s start from cell (X,Y). There are 3 possible cells from which we can come to (X,Y) (assuming they don’t violate the bounds of the array): cells (X-1, Y), (X, Y-1) and (X-1, Y-1). Now we find the minimum cost to reach these three cells. Here, we observe that this problem exhibits optimal substructure, i.e. this problem can be divided into smaller subproblems that do not overlap.

Create a recursive function minCost(int X, int Y), that computes the minimum cost it takes to reach cell (X,Y) from (1,1). The base case would be for cell (1,1) itself.

Space Complexity: OtherExplanation:

O(X + Y), where X and Y are the coordinates of the destination cell.

A record of all recursive calls is maintained in a recursion stack.

Time Complexity: OtherExplanation:

O(3^(X*Y)), where X and Y are the coordinates of the destination cell.

There are X*Y cells to consider (we don’t consider the whole matrix), and from each cell we can move to 3 other cells.

Accepted Answer

Memoization Method

If you draw the recursion tree of all the function calls, you notice that the results of some cells get computed repeatedly. Instead of recomputing it, again and again, we instead store it in a 2D array, so that whenever we require the results later, we can just obtain them from this array. This saves a lot of time.

Space Complexity: OtherExplanation:

O(X*Y), where X and Y are the coordinates of the destination cell.

Minimum costs for all cells need to be maintained in an X*Y matrix.

Time Complexity: OtherExplanation:

O(X*Y), where X and Y are the coordinates of the destination cell.

There are X*Y cells to consider (we don’t consider the whole matrix). Results for each cell take O(1) to compute, now that we store the previous results.

Accepted Answer

Iterative DP Approach

For each cell, let’s compute the answer in a top-down fashion, starting from the top leftmost cells. We create a ‘dp’ table of dimensions X*Y to store these results.

As we compute the results for the top leftmost cells first, when we come to cell (i, j), we already have the results for cells (i-1, j), (i, j-1) and (i-1, j-1) stored in the dp table (provided they do not violate the matrix boundaries). This allows us to compute results for the current cell in O(1) time.

Space Complexity: OtherExplanation:

O(X*Y), where X and Y are the coordinates of the destination cell.

Minimum costs for all cells need to be maintained in an X*Y matrix.

Time Complexity: OtherExplanation:

O(X*Y), where X and Y are the coordinates of the destination cell.

There are X*Y cells to consider (we don’t consider the whole matrix). Results for each cell take O(1) to compute, now that we store the previous results.

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 from cell (x,y) and ends at the top left corner (1,1).

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:

Input Format:

Output Format:

Note:

Constraints:

Top Cisco Consultant Engineer interview questions & answers

Popular interview questions of Consultant Engineer

Top HR questions asked in Cisco Consultant Engineer