Unique Paths

Count paths from the top-left to bottom-right when moves can only go right or down.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Unique Paths: Sweep a 3 by 3 grid row by row; each interior count is old ways[col] from above plus new ways[col-1] from the left.

Input and goalCount paths from the top-left to bottom-right when moves can only go right or down.

Initialize the first rowFor a 3 by 3 grid, ways = [1,1,1] because each top-row cell has exactly one all-right path from the start.

1start/current11??????

rollingRow[1,1,1]

Recognize it

Use it when movement forms an acyclic grid and every path into a cell must arrive through a small fixed set of predecessor directions such as above and left.

Keep true

During a row sweep, ways[col] before update is the count from above and ways[col-1] after update is the count from the left; their sum is the current cell count.

Reuse it

When dependencies come from the previous row and current row prefix, sweep in the direction that preserves both and compress the grid to one mutable row.

Pattern: Grid DP stored as one row.

Simple idea: Every cell can be reached from above or from the left. The old value in the array is the count from above. The new value to its left is the count from the left.

def unique_paths(rows: int, cols: int) -> int:
   ways = [1] * cols
   for _ in range(1, rows):
      for col in range(1, cols):
         ways[col] += ways[col - 1]
   return ways[-1]

Cost: $O(rows\times cols)$ time and $O(cols)$ space.