All problems

Unique Paths

Medium · dynamic programming

A robot stands in the top-left cell of a board with m rows and n columns. It wants to reach the bottom-right cell. On every move it may go one cell down or one cell right, never up or left, and it must stay on the board.

Return how many different routes lead from the top-left cell to the bottom-right cell. Two routes are different if they visit a different sequence of cells.

Examples

Example 1

Input: m = 3, n = 3

Output: 6

Every route has 2 moves down and 2 moves right, and there are 6 ways to order them.

Example 2

Input: m = 2, n = 4

Output: 4

The single downward move can happen at any of the 4 columns.

Example 3

Input: m = 1, n = 5

Output: 1

A single row leaves only one route: keep going right.

Constraints

• 1 <= m, n <= 16
• The answer always fits in a 32-bit signed integer.