Unique Paths

Count the number of ways to move from top-left to bottom-right in a grid.

Pattern fit

Every cell depends only on the ways from its top and left neighbors, making it a clean 2D DP starter.

Key observation

The robot's path into a cell can only come from one of two predecessor cells.

Target complexity

O(mn) / O(mn)

How to break down the solution cleanly

Every cell depends only on the ways from its top and left neighbors, making it a clean 2D DP starter.

The robot's path into a cell can only come from one of two predecessor cells.

Name the state in plain language.

List the decisions that can transition into the state.

Reference implementation

Python

# Generic pattern template
# 1D DP
dp = [0] * (n + 1)
dp[0] = base
for i in range(1, n + 1):
    dp[i] = transition(dp, i)

# 2D DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        dp[i][j] = transition(dp, i, j)