Medium — Dynamic Programming | Math | Combinatorics | Grid

The Problem

Find the number of unique paths from the top-left corner to the bottom-right corner of an m x n grid, where you can only move right or down.

Approach

Use dynamic programming with a 2D table where each cell represents the number of ways to reach that position. Initialize the first row and column to 1, then fill each cell as the sum of paths from the cell above and to the left.

Time: O(m * n) · Space: O(m * n)

Code

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # Initialize a 2D dp grid of size m x n with all values set to 1.
        dp = [[1] * n for _ in range(m)]

        # Fill in the dp grid using dynamic programming.
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        # The value in dp[m-1][n-1] represents the number of unique paths.
        return dp[m - 1][n - 1]

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment