The problem. A robot starts in the top-left corner of an m × n grid and can only move right or down. How many different paths reach the bottom-right corner?
m = 3, n = 7 -> 28
m = 3, n = 2 -> 3 (right-down-down, down-right-down, down-down-right)
m = 1, n = 1 -> 1In grid DP the state is a cell (r, c), and the moves allowed (usually right and down) mean a cell depends only on the cell above and the cell to the left. Filling the table row by row, left to right, always has both ready. The answer sits in the bottom-right corner, and because each row only reads the row above, the table shrinks to one row. This chapter counts paths, counts them around obstacles, minimises a cost along a path, and finds the largest square.
The last move into cell (r, c) came from above or from the left, so paths[r][c] = paths[r − 1][c] + paths[r][c − 1]. Cells in the top row or the left column can only be reached one way — straight along the edge — so they're 1.
function uniquePaths(m, n) { const paths = (r, c) => { if (r === 0 || c === 0) return 1; // along an edge: one way return paths(r - 1, c) + paths(r, c - 1); // from above, or from the left }; return paths(m - 1, n - 1);}Time O(2^(m+n)), space O(m + n). The same cells are counted again and again.
Each cell adds the paths from above and from the left, row by row.
function uniquePaths(m, n) { const paths = Array.from({ length: m }, () => new Array(n).fill(1)); // edges: one way for (let r = 1; r < m; r++) { for (let c = 1; c < n; c++) { paths[r][c] = paths[r - 1][c] + paths[r][c - 1]; // from above, or from the left } } return paths[m - 1][n - 1];}Time O(m · n), space O(m · n).
Row r only reads row r − 1. Keep one row: before the update, row[c] still holds the value from above, and row[c − 1] already holds the new value from the left — exactly the two numbers needed, so the update runs left to right.
function uniquePaths(m, n) { const row = new Array(n).fill(1); for (let r = 1; r < m; r++) { for (let c = 1; c < n; c++) row[c] += row[c - 1]; // above (old row[c]) + left (new row[c - 1]) } return row[n - 1];}Time O(m · n), space O(n).
Every path is m − 1 downs and n − 1 rights in some order, so the count is the number of ways to choose where the downs go: C(m + n − 2, m − 1). Multiply and divide step by step to stay in integers.
function uniquePaths(m, n) { let result = 1; for (let i = 1; i <= m - 1; i++) { result = (result * (n - 1 + i)) / i; // C(n - 1 + i, i), exact at every step } return Math.round(result);}Time O(min(m, n)), space O(1) — with m as the smaller side. Neat, but only works when every cell is open; the DP handles obstacles (next lesson).
