InterviewHubPRO
Section Overview
Q97

Question 97 of 100

Part 11: Dynamic Programming & Knapsack (91 - 100)

97%
DSA Patterns (Multi-Lang)•Part 11: Dynamic Programming & Knapsack (91 - 100)

Unique Paths.

In Simple Words: Paths to cell (r, c) equal paths(r - 1, c) + paths(r, c - 1). Optimize to single row of length $N$: row[c] += row[c - 1].

  • Time: $O(M \cdot N)$ | Space: $O(N)$
Multi-Language Solutions
Switch tabs or choose All
def uniquePaths(m: int, n: int) -> int:
    row = [1] * n
    for _ in range(m - 1):
        new_row = [1] * n
        for j in range(1, n):
            new_row[j] = new_row[j - 1] + row[j]
        row = new_row
    return row[-1]
Previous Question (96)

Word Break.

Next Question (98)

Longest Common Subsequence (LCS).