Unique PathsMedium

Unique Paths

Medium 16.8k64% acceptance

MathDynamic ProgrammingCombinatorics

A robot starts in the top-left corner of an m × n grid. It can move only right or down by one cell at a time, and wants to reach the bottom-right corner.

Return the number of distinct paths the robot can take.

Example 1

Input: m = 3, n = 7

Output: 28

Example 2

Input: m = 3, n = 2

Output: 3

From the top-left of a 3×2 grid there are exactly three corner-to-corner routes: down-down-right, down-right-down, and right-down-down.

Example 3

Input: m = 1, n = 1

Output: 1

Constraints

1 ≤ m, n ≤ 100
The answer is guaranteed to fit in a 32-bit signed integer.

Asked atAmazonGoogleBloombergApple

JavaScript

⌘↵ to run

Loading editor…

Case 1

3, 7

expected: 28

Case 2

3, 2

expected: 3

Case 3

1, 1

expected: 1

Case 4

7, 3

expected: 28

Case 5

10, 10

expected: 48620

Case 6

1, 100

expected: 1

Case 7

4, 5

expected: 35