223. Paths Through a Grid
Challenge1000 ms256 MBSolved by 0%
You are at the top-left corner of an m by n grid and want to reach the
bottom-right. You may only move right or down.
Print how many distinct paths there are.
The recursion is direct: the number of paths to a cell is the number of paths to the cell above it plus the number to the cell on its left. Cells in the top row and left column have exactly one path.
Written plainly this recomputes the same cells enormously many times. A grid of 20 by 20 has about 35 billion paths and only 400 cells, which tells you exactly what to store.
Constraints - `1 ≤ m ≤ 20` - `1 ≤ n ≤ 20`
Input
A single line containing two integers m and n, the number of rows and columns.
Output
Print one integer, the number of distinct paths.
Input3 3
Output6
Noteis a small grid you can draw and count
Input1 1
Output1
Noteis a single cell, where you are already at the destination
Hint 1Approach
Hint 2Approach
Hint 3Pseudocode
Hint 4Full solution