💬 Discord
Sign In
NeetCode #712LC-62Medium2-D Dynamic ProgrammingBlind 75NC 150NC 250
← Back to All Problems

#712 · #62 · Unique Paths(不同路径)

📌 Problem Statement & Constraints

A robot starts at the top-left of an m x n grid and may move only right or down. Return the number of distinct paths to the bottom-right corner. Constraints: 1 <= m, n <= 100.

💡 Core Algorithmic Approaches

  1. dp[i][j] is the number of paths reaching cell (i, j).
  2. Every path arrives either from above or from the left, so dp[i][j] = dp[i-1][j] + dp[i][j-1].
  3. The first row and first column each have exactly one path, since there is only one direction to travel along them.
  4. Only the previous row is needed, so the space reduces to O(n).

💻 Benchmark Python3 Implementation

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n                   # first row: one way to each cell
        for _ in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j - 1]     # above (dp[j]) + left (dp[j-1])
        return dp[n - 1]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): every cell is visited once.
💾 Space Complexity
O(n): a single rolling row.

⚠️ Interview Pitfalls & Follow-ups

  • Initialising the whole table to 1: only the first row and column are 1; interior cells must be computed.
  • Fearing the in-place update: dp[j] += dp[j-1] is correct because dp[j-1] has already been updated for the current row.
  • Off-by-one on the loops: the outer loop runs m - 1 times and the inner loop covers the remaining n - 1 columns.
  • Using combinatorics carelessly: C(m+n-2, m-1) works but risks overflow in fixed-width languages.