CODEWITHSUNDEEP
c#algorithm
smatter
smatter

Reputation: 29218

Corner to corner shortest paths in a rectangular grid

I came across this question for an interview that I could not solve. Code to calculate the number of shortest paths from botton left to upper right corner of an mxn grid. How to solve this?

Upvotes: 2

Views: 3365

Answers (3)

amit
amit

Reputation: 178491

This problem is a private case of this question, where you limit yourself only to all passes that end with the upper-right corner.

For simplixty, let's assume n * n matrix [it can be generalized to m * n later.
Note that each path from one corner to the other has excactly 2n moves, out of them - exactly n moves are "up" and the rest are "right"

So, you can represent your paths with all binary vectors of length 2n with exactly n bits set to 1.

The number of such binary vectors can be calculated with a close formula in O(1): choose(2n,n).

To generalize it to n * m matrix: Think, how many steps are there in the path from one corner to the other? How many of them are "right"? imply the choose formula to the new matrix, and make sure that it gives you the same result we got before for n=m

Upvotes: 2

Alexei Levenkov
Alexei Levenkov

Reputation: 100545

Assuming you want to solve it, but not the solution: consider 1x1, 1x2, (m-1)x(n-1)

Upvotes: 4

ivancho
ivancho

Reputation: 899

https://en.wikipedia.org/wiki/Dynamic_programming

https://en.wikipedia.org/wiki/Memoization

Upvotes: 2

Related Questions