Unique Paths

A robot starts at the top-left of an m x n grid and can only move right or down. Return the number of unique paths to the bottom-right. Brute-force path enumeration is exponential.

Why this is worth learning

Classify paths by their final move into a cell. Right/down movement makes the grid acyclic, so path counts can be accumulated in row-major order.

Before coding: one-minute experiment

How many paths cross a 3-by-3 grid, and why does dp[c] need its old value before the update?

Function signature

func UniquePaths(m, n int) int

Inputs / outputs

• m, n: grid dimensions.
• Return: number of unique paths.

Example

m = 3, n = 7
Output: 28

Constraints

• 1 <= m, n <= 100
• The number of paths is guaranteed to fit the target Go int. This is an additional input guarantee; the dimension bounds alone do not imply it.

Core idea (near-solution)

DP where each cell's count is the sum of the counts from the cell above and to the left.

Invariant: before updating an interior column c>0, dp[c] still stores the previous row’s path counts from above, while dp[c-1] already stores the current row’s value from the left. After the write, dp[c] has the current cell’s answer.

Algorithm (step-by-step)

1. Initialize a 1D array dp with all 1s (first row).
2. For each remaining row:
   • For each column c from 1..n-1, update dp[c] += dp[c-1].
3. Return dp[n-1].

Correctness sketch

Let P(r,c) count paths from the top-left to (r,c). Except for the start, every path enters from above or from the left, and these final-move classes are disjoint. Therefore P(r,c)=P(r-1,c)+P(r,c-1), with out-of-grid predecessors contributing zero and the start contributing one. In an obstacle-free grid, each first-row or first-column cell has one path. During a left-to-right row update, dp[c] still stores the previous-row value from above and dp[c-1] already stores the current-row value from the left. Their sum is the required new count.

Trace (hand walkthrough)

Example input:
m = 3, n = 7
Output: 28

Walk:
- row0: [1,1,1,1,1,1,1]
- row1: [1,2,3,4,5,6,7]
- row2: [1,3,6,10,15,21,28] -> 28

Pitfalls to avoid

• Forgetting the first row/column are all 1s (only one way along edges).
• Using 2D dp when 1D is sufficient.

Debugging lens

Test one row, one column, and symmetric dimensions. A 100-by-100 grid has far more paths than a 64-bit int can hold; dimension limits alone do not establish representability.

Complexity

• Time: O(m*n).
• Extra space: O(n).

Implementation notes (Go)

• Use int under the stated representable-count guarantee. An unobstructed 100-by-100 grid exceeds signed 64-bit counting and is outside that guarantee.

Contract precision

For an unobstructed grid, every prefix-cell count is at most the destination count, so the answer guarantee also bounds the intermediate additions. The function does not report overflow for inputs outside that guarantee.

Reconstruction checkpoint

How many paths cross a 3-by-3 grid, and why does dp[c] need its old value before the update?

Return to 2D DP · Module quiz