Unique Paths

Medium~20 min

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Examples

Example 1

Input: m = 3, n = 7

Output: 28

Explanation: From the top-left to bottom-right of a 3x7 grid, there are 28 unique paths.

Example 2

Input: m = 3, n = 2

Output: 3

Explanation: There are three paths: Right→Down→Down, Down→Down→Right, Down→Right→Down.

Example 3

Input: m = 1, n = 1

Output: 1

Explanation: The robot is already at the destination. There is only one path (stay).

Constraints

1 <= m, n <= 100
Expected time complexity: O(m × n)

Code

Ctrl+EnterRun|Ctrl+⇧+EnterSubmit

Output

Run your code to see results

Use Cmd+Enter to run