A grid has m rows and n columns. A token starts in the top-left cell and has to reach the bottom-right cell. Each move takes it one cell right or one cell down; it can never move left or up.
Return the number of different routes the token can take from start to finish.
Example 1
Input: m = 3, n = 3
Output: 6
Every route makes 2 moves down and 2 moves right, in some order: RRDD, RDRD, RDDR, DRRD, DRDR and DDRR.
Example 2
Input: m = 2, n = 5
Output: 5
The single move down can come before any of the 4 moves right, or after all of them.
Example 3
Input: m = 1, n = 8
Output: 1
With one row there is only one way: straight to the right.
Constraints
1 <= m, n <= 1002 × 10⁹, so it fits in a 32-bit signed integer.The last move into any cell comes either from the cell above it or from the cell to its left, so the routes to a cell are the routes to those two cells added together.
Look at the very last move of any route into a cell. The token can only arrive from the cell directly above or from the cell directly to the left. Those two groups of routes never overlap, since they end with different moves, and together they are all the routes. So:
Time O(m · n)Space O(n)
The full walkthrough and code are part of Premium
3
6