Unique Paths in a Grid

mediumSave

CombinatoricsDynamic ProgrammingMatrix

Imagine a robot sitting on the top-left corner of a grid (m x n). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. Write a function to return the number of unique paths that the robot can take to reach the destination.

Your task is to complete the function unique_paths which takes two integers m and n, representing the number of rows and columns in the grid respectively.

Example 1

Input

[
  3,
  7
]

Output

Explanation. There are 28 unique paths from the top-left corner to the bottom-right corner in a 3x7 grid.

Example 2

Input

[
  3,
  2
]

Output

Explanation. There are 3 unique paths (right-right-down, right-down-right, down-right-right) in a 3x2 grid.

Example 3

Input

[
  7,
  3
]

Output

Explanation. There are 28 unique paths from the top-left to the bottom-right in a 7x3 grid, demonstrating the symmetry in path choices.

Follow-up: Can you solve this problem using both a dynamic programming approach and a combinatorial approach? Discuss the time and space complexity of both methods.

Constraints:

1. 1 <= m, n <= 100 2. The answer is guaranteed to fit in a 32-bit integer.

Views: 2