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

Tested only

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

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?