Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: Given two dimen­sional matrix, write an algo­rithm to count all pos­si­ble paths from top left cor­ner to bottom-right cor­ner. You are allowed to move only in two direc­tions, move right OR move down.

Exam­ple:No Of Paths

Approach:

Recur­sion– Ear­lier we have seen “Print All Paths from Top left to bot­tom right in Two Dimen­sional Array”. Cur­rent prob­lem is the sub­set of that prob­lem. Here we will just count the num­ber 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 col­umn then there is only one way to reach the last cell is to travel through that row or col­umn. x

Recur­sive Code:

Time Com­plex­ity: It will be expo­nen­tial since we are solv­ing many sub prob­lems repeat­edly. We will use the Bottom-up approach of Dynamic pro­gram­ming and store the results of sub prob­lems to reuse them in future.

Dynamic Pro­gram­ming Code:

Out­put:

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

You may also like...

  • crack­er­place

    The countDP method is not top down dp right as you are not doing any mem­o­iza­tion ?Its bot­tom top DP I believe ?

    • Pintu Das

      I agree with you mate.

      • tuto­ri­al­hori­zon

        Yes it is bottom-up. I have cor­rected it. Thanks

    • tuto­ri­al­hori­zon

      Yes it is bottom-up. I have cor­rected it. Thanks for point­ing it out. Please do let me know if you find prob­lems in other articles.

  • MANH LE VAN

    Hi every­one! i’m look­ing for server like SPOj.com to sub­mit solu­tion for this exam­ple. Please help me, thank you very much!

  • Pintu Das

    The above solu­tion is the bottom-up approach as we are using the solu­tion of smaller prob­lems in the larger ones.

  • Alexa

    Well, if the goal is just to cal­cu­late the num­ber of paths. There’s a much sim­pler (and more maths-centric) way:

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

    The sim­ple “proof” is this: You have to go across (move to the right) exact column-1 times and you have to move down­ward exactly row-1 times. (-1 because you don’t count the start­ing cell)

    So it’s back a sim­ple com­bi­na­to­r­ial math prob­lem of hav­ing choos­ing x ele­ments and y ele­ments to make a (x+y) series.

  • Sivaram

    I came across an inter­view ques­tion which is sim­i­lar to this prob­lem.
    A point P(x,y) is given. This point rep­re­sents the coor­di­nates in the matrix.
    Then count all the paths from top left to the given point and from that point to bot­tom right cor­ner of the matrix.
    Could you please explain how to approach this prob­lem.
    I thought it would be two sub prob­lems of this prob­lem.
    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 bot­tom right cor­ner of the matrix using the same approach.

    Could you advise if this is bet­ter way or is there a more neat solution?