Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtwo-dimensional-dp

Unique Paths

Problem (restated)

Robot at top-left of m×n grid can only move right or down. How many paths to bottom-right?

Intuition

dp[r][c] = from top + from left; borders are 1.

Approaches

2D DP

Unverified

Time O(m*n)Space O(n)

Idea. Roll one row; dp[c] += dp[c-1].

Walkthrough. m=3,n=7 → 28.

Trade-offs. Combinatorics C(m+n-2,m-1) also works.

Solution

export function uniquePaths(m: number, n: number): number {
  const dp = new Array<number>(n).fill(1);
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) dp[c] = dp[c]! + dp[c - 1]!;
  }
  return dp[n - 1]!;
}

export function uniquePaths(m: number, n: number): number {
  const dp = new Array<number>(n).fill(1);
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) dp[c] = dp[c]! + dp[c - 1]!;
  }
  return dp[n - 1]!;
}

Template connection

Two-dimensional DP grid.

Reflection

Moves are only right and down. A cell is the ways from above plus the ways from the left. The first row and the first column are 1. One rolling row is the same update: dp[c] += dp[c - 1].
m = 1 or n = 1 is a single path, so the answer is 1. There are no obstacles.
Cell (0, 0) is 1. A wide grid must not overflow the running total.