Unique Paths
Medium2-D dynamic programming
A robot stands in the top-left cell of a grid with m rows and n columns. Each move takes it one cell right or one cell down.
Return how many different routes take it to the bottom-right cell.
Examples
Input: m = 2, n = 4 Output: 4
The one move down can come in any of the 4 columns.
Input: m = 3, n = 3 Output: 6
Two moves right and two down, in any order: RRDD, RDRD, RDDR, DRRD, DRDR and DDRR.
Constraints
1 ≤ m, n ≤ 100- The answer is at most
2 × 10⁹.
Stuck?
Hint 1
The robot reaches a cell from the cell above it or the cell to its left, so the routes to a cell are the routes to those two added up.
Hint 2
Every cell in the top row and the left column has exactly one route. Fill the grid row by row; one row of counts is enough.
The idea
The robot enters a cell from above or from the left, so the routes to a cell are the routes to the cell above plus the routes to the cell on its left. Filling the grid row by row needs only the row above, and that row can be updated in place.
Time O(m · n)Extra space O(n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
The top row: each of its cells is reached in exactly one way, by moving right the whole time.
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]; } } return row[n - 1];}The trap
Counting routes with a formula is a good idea: the robot makes m - 1 moves down and n - 1 moves right, and a route is the choice of which moves are down. The wrong solution builds that count with n + i where it needs n - 1 + i, so it counts the routes of a grid with one column more. A grid of one row skips the loop and still gives 1, which hides the slip, but every taller grid gets too many routes.
function uniquePaths(m, n) { let routes = 1; for (let i = 1; i < m; i++) routes = (routes * (n + i)) / i; // should be n - 1 + i return Math.round(routes);}