Problem 1483. Number of paths on a grid
Consider a grid formed by n vertices vertically down, and m vertices horizontally right. Your starting point is at the top left vertex. Your destination is the bottom right vertex. You are permitted at each vertex to choose to move down or right, that is in the direction towards the destination. You are not to move on what constitutes a back step like moving left or up. If you hit the bottom boundary, or right boundary take it to be given there is only 1 way to the destination, that is following along the boundary.
Ex: in a 2x2 grid there are two ways. One way: First down, then right. The other way: First right, then down.
4x3 has 10 ways
6x5 has 126 ways
This problem can be solved using dynamic programming but there are other methods too.
Solution Stats
Problem Comments
-
5 Comments
Show
2 older comments
Tim
on 2 May 2013
It would be more elegant to define the solution for the 1x1 case as 1 rather than 0.
G K
on 11 May 2013
agree, but will leave as so, so as to not affect submitted solutions.
Rafael S.T. Vieira
on 20 Jul 2020
I disagree with the base case. A 1x1 matrix has 1 path. And, the empty matrix has no path (zero).
goc3
on 28 Sep 2020
The first test case has been changed from 0 to 1 without rescoring past solutions.
Tyler
on 13 Jul 2022
Very interesting problem when you think about it.
Solution Comments
Show commentsProblem Recent Solvers71
Suggested Problems
-
4056 Solvers
-
Back to basics 11 - Max Integer
780 Solvers
-
267 Solvers
-
221 Solvers
-
4786 Solvers
More from this Author10
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!