Unique Paths

Medium

dynamic-programming

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.

Recurrence Relation: dp[i][j] = dp[i-1][j] + dp[i][j-1]

The number of ways to reach cell (i,j) is the sum of ways to reach the cell above and the cell to the left.

Base Case: dp[0][j] = 1 and dp[i][0] = 1 (only one way to reach any cell in the first row or column).

Example 1

Input: m = 3, n = 7

Output: 28

Explanation: From the top-left to bottom-right, there are 28 unique paths.

Example 2

Input: m = 3, n = 2

Output: 3

Explanation: From the top-left corner, there are 3 ways to reach the bottom-right corner: Right -> Down -> Down, Down -> Down -> Right, Down -> Right -> Down.

Example 3

Input: m = 1, n = 1

Output: 1

Explanation: Already at the destination.

Constraints

•1 <= m, n <= 100

Show Hints (4)

Hint 1: Think about how you can reach any cell (i, j).

Hint 2: You can only come from the cell above (i-1, j) or from the left (i, j-1).

Hint 3: The first row and first column have only one way to reach each cell.

Hint 4: Build the solution bottom-up, filling the grid row by row.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?