Objective: Given two dimensional matrix, write an algorithm to count all possible paths from top left corner to bottom-right corner. You are allowed to move only in two directions, move right OR move down.

From every cell you will have two options to make a move, either to go right OR down. Base case will be check if you have reached to either last row OR last column then there is only one way to reach the last cell is to travel through that row or column. x

Recursive Code:

Time Complexity: It will be exponential since we are solving many sub problems repeatedly. We will use the Bottom-up approach of Dynamic programming and store the results of sub problems to reuse them in future.

Dynamic Programming Code:

Output:

No Of Path (Recursion):- 6
No Of Path (DP):- 6

__________________________________________________ Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________