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.

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

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: dp[c] holds the number of paths to the current row's column c.

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

• Invariant: dp[c] holds the number of paths to the current row's column c.
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

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.

Complexity

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

Implementation notes (Go)

• Use int; values fit within constraints.