Q:

Given a M X N matrix with initial position at top-left cell, find the number of possible unique paths to reach the bottom right cell of the matrix from the initial position

mahmoud2506
Save to bookmark
|
2022-04-30
|
  278 
0

Number of Unique Paths

Given a M X N matrix with initial position at top-left cell, find the number of possible unique paths to reach the bottom right cell of the matrix from the initial position. Possible moves can be either down or right at any point in time.

    Input:
    The first line contains an integer T, 
    depicting total number of test cases. 
    Then following T lines contains two integers 
    m and n depicting the size of the grid.
    
    Output:
    Print the number of unique paths to reach 
    bottom-right cell from the top-left cell.

Example with explanation:

    Input:
    2
    3 3
    3 4

    Output:
    6
    10

So, for the first test case, M=3, n=3

Grid is like,

Number of Unique Paths (1)

1. (0,0)->(0,1)->(0,2)->(1,2)->(2,2)

Number of Unique Paths (2)

2. (0,0)->(0,1)->(1,1)->(1,2)->(2,2)

Number of Unique Paths (3)

3. (0,0)->(0,1)->(1,1)->(2,1)->(2,2)

Number of Unique Paths (3)

4. (0,0)->(1,0)->(2,0)->(2,1)->(2,2)

Number of Unique Paths (5)

5. (0,0)->(1,0)->(1,1)->(1,2)->(2,2)

Number of Unique Paths (6)

6. (0,0)->(1,0)->(1,1)->(2,1)->(2,2)

Number of Unique Paths (7)

This are the possible unique paths and hence count is 6.

Given a matrix with an initial position at the top-left cell, find the number of possible unique paths to reach the bottom-right cell of the matrix from the initial position. Possible moves can be either or at any point in time.

C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-04-30
need an explanation for this answer? contact us directly to get an explanation for this answer

Recursion Algorithm:

    Of course, we can generate a recursion algorithm.
    Since the only possible moves are down and right 
    from any point, we can write a recursive relation,

    f(m,n) = f(m-1,n) + f(m,n-1)
    Where f(m,n) = number of unique path for grid size m,n
    f(m-1,n) = number of unique path for grid size [(m-1),n] 
    a down move from the end point of this will result in f(m,n)
    f(m,n-1) = number of unique path for grid size [m,(n-1)] 
    a right move from the end point of this will result in f(m,n)
    Hence, f(m,n) is summation of f(m-1,n) and f(m,n-1)

So, the algorithm can be:

    Function Uniquepaths(m,n):
        1)  If m==0 & n==0 return 0
        2)  If m == 0
                Then return 1
        3)  If n==0
                Then return 1
        4) Return Uniquepaths(m-1,n)+Uniquepaths(m,n-1)

But this would generate many overlapping subproblems, which will be computed again and again increasing the time complexity. Hence, we can convert the recursion to dynamic Programming.

Dynamic Programming approach:

    1)  Create a 2D array DP with size m, n
    2)  Initialize DP[0][0] =0 which is similar to step 1 in our previous function.
    3)  for i=1 to n-1
            DP[0][i]=1
        end for
        This is similar to step2 in our previous function
    4)  for i=1 to m-1
            DP[i][0]=1
        end for
        This is similar to step3 in our previous function

    5)  Compute the whole DP table
        for i=1 to m-1
            for j=1 to n-1
                DP[i][j]=DP[i-1][j]+DP[i][j-1]
            end for
        end for   
        This is similar to step 4 in our previous recursive function
    6)  Return DP[m-1][n-1] which is the result.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

int uniqueRoute(int m,int n){
	int DP[m][n];

	memset(DP,0,sizeof(DP));

	//base cases
	DP[0][0]=0;

	for(int i=1;i<m;i++)
		DP[i][0]=1;

	for(int i=1;i<n;i++)
		DP[0][i]=1;
	
	//compute dp table
	for(int i=1;i<m;i++){
		for(int j=1;j<n;j++){
			DP[i][j]=DP[i-1][j]+DP[i][j-1];
		}
	}
	return DP[m-1][n-1];
}

int main()
{
	int t,n,m;

	cout<<"Enter number of testcases\n";
	cin>>t;

	for(int i=0;i<t;i++){
		cout<<"Enter grid size, m & n\n";
		cin>>m>>n;
		cout<<"Number of unique paths from topleft to bottom right: "<<uniqueRoute(m,n)<<endl;
	}

	return 0;
}

Output

 

Enter number of testcases
2
Enter grid size, m & n
3 3
Number of unique paths from topleft to bottom right: 6
Enter grid size, m & n
3 4
Number of unique paths from topleft to bottom right: 10

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | dynamic programming
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Given two strings S and T, find the number of time... >>
<< Given an array of integers where each element repr...