Dynamic Programming – Count all paths from top left to bottom right of a mXn matrix

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.

Example:No Of Paths


Recursion- Earlier we have seen “Print All Paths from Top left to bottom right in Two Dimensional Array“. Current problem is the subset of that problem. Here we will just count the number of paths, will not print them.

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:


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

8 thoughts on “Dynamic Programming – Count all paths from top left to bottom right of a mXn matrix”

  1. The countDP method is not top down dp right as you are not doing any memoization ?Its bottom top DP I believe ?

  2. Hi everyone! i’m looking for server like SPOj.com to submit solution for this example. Please help me, thank you very much!

  3. Well, if the goal is just to calculate the number of paths. There’s a much simpler (and more maths-centric) way:

    nWays = (biomial(row-1, row+column -2) + binomial(column – 1, row+column -2 ) / 2

    The simple “proof” is this: You have to go across (move to the right) exact column-1 times and you have to move downward exactly row-1 times. (-1 because you don’t count the starting cell)

    So it’s back a simple combinatorial math problem of having choosing x elements and y elements to make a (x+y) series.

  4. I came across an interview question which is similar to this problem.
    A point P(x,y) is given. This point represents the coordinates in the matrix.
    Then count all the paths from top left to the given point and from that point to bottom right corner of the matrix.
    Could you please explain how to approach this problem.
    I thought it would be two sub problems of this problem.
    Firstly count all paths from top left to the given point using this approach.
    Then start from the given point and count the paths to the bottom right corner of the matrix using the same approach.

    Could you advise if this is better way or is there a more neat solution?


Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.