Unique Paths in a Grid

mediumSave

CombinatoricsDynamic ProgrammingMath

Given an MxN grid, count how many unique paths there are from the top-left corner to the bottom-right corner. You can only move either down or right at any point in time. The grid dimensions M and N will be provided as input.

Example 1

Input

[
  2,
  3
]

Output

Explanation. The three paths are: right-right-down, right-down-right, down-right-right.

Example 2

Input

[
  3,
  3
]

Output

Explanation. The paths include combinations of rights and downs three times each, but in different orders (e.g., DRR, RDR, RRD, DRRD, DRDR, DDRR).

Example 3

Input

[
  1,
  1
]

Output

Explanation. The only path is to stay at the origin since you're already at the destination.

Example 4

Input

[
  7,
  3
]

Output

Explanation. There are 28 unique ways to reach the bottom-right corner, which involves moving down 2 times and right 6 times in various orders.

Follow-up: Can you solve this problem using less than O(M*N) space?

Constraints:

1 \u2264 M, N \u2264 100

Views: 3