leninkumar31's blog

Number of paths in grid
By leninkumar31, history, 4 years ago, In English

Following question was asked in a coding interview.how to solve it with out using dynamic programming?

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (6)
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by leninkumar31 (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

To reach from (0,0) to (X,Y) you need to go right X steps and go up Y steps. Let's regard a step as an arrow. If there is no building, you can make combinations of X right-arrows and Y up-arrows. That's C(X+Y,X) or equivalently C(X+Y,Y).

Now, there is a building that covers (A,B) to (A+N,B+M). Let f(X,Y) be the number of combinations can be made with X right-arrows and Y up-arrows. That is, f(X,Y) = C(X+Y,X) = C(X+Y,Y).

Then the number of pathes is as follows:

f(X,Y) — f(A+1,B+1)f(M-2,N-2)f(X-A-N+1,Y-B-M+1)

  • special case: f(x,y) = 0 where x < 0 or y < 0.
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you explain last equation in detail?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      In fact it's wrong. I'm finding a new formula. But the idea was:

      p = the number of pathes from (0, 0) to (A+1, B+1)
q = the number of pathes from (A+1, B+1) to (A+N-1, B+M-1)
r = the number of pathes from (A+N-1, B+M-1) to (X,Y)
the number of pathes can't be taken = pqr
      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

A path should contain exactly one of arrows in the picture. (there are A up-arrows and B right-arrows)

  • The number of pathes that contain u1 is f(0,B+M-1)f(X,Y-B-M)
  • The number of pathes that contain u2 is f(1,B+M-1)f(X-1,Y-B-M)
  • ...

So, the answer is:

→ Reply