62. Unique Paths

A robot starts at the top-left of an m × n grid and can only move down or right. How many unique paths lead to the bottom-right corner?

Every path makes (m−1) down moves and (n−1) right moves. Choose which of the m+n−2 moves go down: C(m+n−2, m−1).

1function uniquePaths(m: number, n: number): number {
2  const total = m + n - 2, k = Math.min(m, n) - 1;
3  let res = 1;
4  for (let i = 1; i <= k; i++) {
5    res = (res * (total - k + i)) / i;
6  }
7  return Math.round(res);
8}

total = 8k = 2res = 1

Choose 2 of 8 moves: C(8, 2).

1 / 0

Space: play/pause · ←/→: step