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?
Asked
Active
Viewed 3,042 times
2
-
http://stackoverflow.com/questions/9105699/algorithm-for-finding-all-paths-in-a-nxn-grid http://stackoverflow.com/questions/9172053/all-possible-moves-in-a-5x5-grid http://stackoverflow.com/questions/9051254/finding-points-in-a-grid-with-exactly-k-paths-to-them There was at least THREE same questions in two weeks. Did you try to use search? – OleGG Feb 10 '12 at 08:03
3 Answers
4
Assuming you want to solve it, but not the solution: consider 1x1, 1x2, (m-1)x(n-1)
Alexei Levenkov
- 98,904
- 14
- 127
- 179
2
ivancho
- 899
- 6
- 10
-
2This answer reminds me of my "Go to" answer when an interviewer tries to stump me with a "How would you solve [x]?". My reply: "With some *math*." – J. Holmes Feb 10 '12 at 02:16
-
The one and only point of an interview question like this is to see whether you are familiar with dynamic programming. I am teaching a man to fish here. – ivancho Feb 10 '12 at 02:22
-
@ivancho: there is absolutely no need to use dynamic programming to solve this particular problem, the solution can be found in O(1) time and space. Hint: the shortest path length is `m+n`, therefore in *any* shortest path there are *exactly* `m` horizontal and `n` vertical steps. But the order can be arbitrary. – Igor Korkhov Feb 10 '12 at 02:37
-
Yes, I can see the math solution too - the OP explicitly said the interview question was about code. And good luck doing the math if your space is not a rectangle, but an arbitrary grid shape. – ivancho Feb 10 '12 at 02:43
-
@ivancho: Different shapes require different approaches, of course, but this nail is too small for the dynamic programming hammer, IMO. If the interviewer wanted to check whether the candidate knows about DP, they would have asked a different question. I believe that this was one of the interview questions where one is expected to think a bit before showing off knowledge of cool paradigms. – Igor Korkhov Feb 10 '12 at 10:16
2
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
