A robot on an m×n grid can only move right or down — count every distinct route to the bottom-right corner using a simple 2D DP recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1], or solve it in O(1) space with a rolling row, or even in O(1) time via the combinatorial formula C(m+n-2, m-1).
A robot starts at the top-left of an m × n grid and must reach the bottom-right. It can only move right or down at each step. How many distinct paths are there?
Concrete example: m=3, n=7 → 28 paths. With m=3, n=3 → 6 paths. You can trace them in the Visualize tab.
dp[i][j] you must have come from dp[i-1][j] (above) or dp[i][j-1] (left) — never both at once. So the number of paths to (i, j) is exactly the sum of paths to those two neighbors: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Base case: every cell in the top row and left column has exactly 1 path.m × n table filled with 1. This seeds the top row and left column in one shot — those edge cells truly have only one path.i from 1 to m-1, for j from 1 to n-1: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Each cell only needs its left and top neighbors, which are already computed.dp[m-1][n-1] holds the answer.fill(0) and trying to handle the base case inside the loop leads to index-out-of-bounds or an answer of 0. The cleanest fix: just fill(1) upfront and start both loops at index 1.Because dp[i][j] only needs row i-1 and the current row up to j-1, you only need to keep one row in memory. Overwrite in place: row[j] += row[j-1] — at that moment row[j]still holds the old "from above" value and row[j-1]was just updated to "from left".
The robot always takes exactly m-1 down-steps and n-1 right-steps, for m+n-2 total moves. The path count equals the number of ways to choose which m-1 of them are "down": C(m+n-2, m-1). For m=3, n=7: C(8, 2) = 28. This runs in O(min(m,n)) time and O(1) space.
3×7 DP table. Seed the entire top row and left column to 1 — there is exactly one way to reach any cell on the edge (go straight).function uniquePaths(m: number, n: number): number {
// dp[i][j] = number of unique paths to reach row i, col j
const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(1));
// Top row and left column are already seeded to 1 (fill(1) above).
// Only one way to reach any edge cell: go straight.
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
// O(1)-space rolling optimisation: one row is enough.
function uniquePathsO1(m: number, n: number): number {
let row = Array(n).fill(1);
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
row[j] += row[j - 1]; // row[j] holds "from above"; row[j-1] just became "from left"
}
}
return row[n - 1];
}
// Combinatorial closed form: C(m+n-2, m-1)
function uniquePathsMath(m: number, n: number): number {
// Robot takes exactly (m-1) down-steps and (n-1) right-steps = m+n-2 total.
// Choose which m-1 of them are down-steps.
const total = m + n - 2;
const choose = m - 1;
let result = 1;
for (let i = 0; i < choose; i++) {
result = (result * (total - i)) / (i + 1);
}
return Math.round(result);
}Array.from({ length: m }, () => Array(n).fill(1)) creates the full grid pre-filled with 1. This implicitly handles the base case: every cell on the top row (i=0) and left column (j=0) correctly holds 1 because there is exactly one path along the edge.1 to skip the already-correct border. The recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1] is safe because both sources are in earlier rows or earlier columns — guaranteed computed.row[j], its current value is the "from above" contribution (carried from the previous outer-loop iteration). After row[j-1] is updated it holds "from left". So row[j] += row[j-1] is exactly the 2D recurrence collapsed to 1D.m+n-2 steps; we choose m-1of them to be "down". That is C(m+n-2, m-1). The loop computes the binomial coefficient in O(k) via the multiplicative formula to avoid factorial overflow.O(n). Walk through row[j] += row[j-1] and explain why the overwrite is safe.0 (no path reaches it). The recurrence is otherwise identical.+ with minand add the current cell's cost: dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]).C(m+n-2, m-1). Mention it shows this is essentially Pascal's triangle and note potential overflow for large inputs (use BigInt or the rolling DP instead).| grid, can only move right/down | 2D DP, dp[i][j] = dp[i-1][j] + dp[i][j-1] |
| count distinct paths on a grid | seed edges to 1, fill interior |
| "reduce space to O(n)" | rolling single row: row[j] += row[j-1] |
| closed-form / combinatorics | C(m+n-2, m-1) — choose down-steps |
function uniquePaths(m: number, n: number): number {
const dp = Array.from({ length: m }, () => Array(n).fill(1));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}m=3, n=3, what is the answer?m=4, n=4 is: