62. Unique Paths

Medium · Dynamic Programming

A robot is located at the top-left corner of an m × n grid. 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. How many distinct paths are there?

Assuming all obstacles are absent and each cell is traversable, count the total number of unique ways the robot can reach the destination.

Examples

Example 1
Input: m = 3, n = 2
Output: 3
Explanation: From a 3×2 grid (3 rows, 2 columns), the robot starts at (0,0) and must reach (2,1). The three paths are: (0,0)→(1,0)→(2,0)→(2,1), (0,0)→(1,0)→(1,1)→(2,1), and (0,0)→(0,1)→(1,1)→(2,1).
Example 2
Input: m = 3, n = 3
Output: 6
Explanation: From a 3×3 grid, there are 6 distinct paths to reach the bottom-right corner from the top-left.

Constraints