Unique Paths

Pascal's Triangle

LRU Cache

Count the distinct top-left to bottom-right paths on a grid moving only right or down.

A robot sits in the top-left cell of an `m x n` grid and wants to reach the bottom-right cell. It may only move **right** or **down** one cell at a time. Return how many distinct paths it can take.

**Input / output**
- Input: `m: integer` (rows), `n: integer` (columns)
- Output: the number of unique paths

**Examples**
1. `m = 3, n = 7` returns `28`.
2. `m = 3, n = 2` returns `3`.
3. `m = 1, n = 1` returns `1`.

**Constraints**
- `1 <= m, n <= 100`
- The answer is guaranteed to fit in a 32-bit signed integer.

**Follow-up**
Can you solve it in `O(min(m, n))` space using the closed-form binomial coefficient `C(m + n - 2, m - 1)` instead of a full DP table?

- The robot only moves right or down, so every path is a sequence of moves.
- Reaching cell `(i, j)` is only possible from `(i-1, j)` (a down move) or `(i, j-1)` (a right move).
- The number of ways to reach a cell is the sum of the ways to reach those two neighbours.

Understand the Pattern

- Build an `m x n` table where `dp[i][j]` is the number of paths to that cell.
- The first row and first column are all `1` (only one straight-line path).
- Every other cell is `dp[i-1][j] + dp[i][j-1]`.

Dynamic Programming Table

- Each row only depends on the row above, so a single 1-D array suffices.
- Iterate rows top to bottom, adding the value to its left in place.
- This drops memory to `O(n)`.

Optimise the Space

- Any path makes exactly `m - 1` down moves and `n - 1` right moves.
- The count is the binomial coefficient `C(m + n - 2, m - 1)`.
- Computing it multiplicatively is `O(min(m, n))` time and `O(1)` space.