Count the routes across a grid with m rows and n columns, from its top-left cell to its bottom-right cell. Each step moves exactly one cell down or one cell right. Return the number of different routes.
Example 1
Input
m = 2, n = 4
Output
4
Explanation
every route takes 1 step down and 3 steps right. The step down can come first, second, third or last, so there are 4 routes.
Example 2
Input
m = 4, n = 4
Output
20
Explanation
every route takes 3 steps down and 3 steps right in some order, and there are 20 such orders.
Example 3
Input
m = 1, n = 1
Output
1
Explanation
the grid is a single cell, so the start is already the finish. The one route makes no steps.
Constraints:
1 <= m, n <= 100
the answer fits in a signed 32-bit integer
Tab indents. Press Esc, then Tab to leave the editor.
Ctrl or ⌘ + Enter runs the tests.
Run your code to see every test here. Nothing is submitted or recorded.