Given an m x n grid, the machine must count the distinct paths a robot takes from the top-left cell to the bottom-right cell, moving only down or right. No obstacles exist, so this is purely combinatorial, but the count grows large enough to require dynamic programming rather than enumeration.
The key insight is that every cell is reachable from exactly two directions: the cell above and the cell to its left. Therefore paths(cell) = paths(above) + paths(left), and the machine can build the count row by row.
The approach runs in three steps. First, seed the first row and first column with 1, since each edge cell has exactly one path leading to it. Second, fill each remaining cell by summing the cell above and the cell to the left. Third, return the bottom-right value. Time is O(m x n) and space is O(n), because only the previous row is needed to compute the next one.
The trickiest edge case is the degenerate 1x1 grid: the start cell is also the goal, and there is exactly one path — the empty route — so the machine must return 1. The row-based seeding handles this automatically, since the single row is initialized entirely to 1.
def uniquePaths(m, n):
row = [1] * n
for _ in range(1, m):
for c in range(1, n):
row[c] += row[c - 1]
return row[-1]