Unique Paths
FreeDynamic programmingMedium59 of 75
The problem
Count paths from the top-left to the bottom-right of an m×n grid, with m,n ≥ 1. Each move goes one cell right or down. There are no obstacles.
Example
m = 2, n = 4 → 4
Need a hint?
A cell can be entered only from above or from the left.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Initialize one row of n counts to one, representing the first row. For each subsequent row, keep its first count one and update each other count by adding its left neighbor. The old value is the contribution from above. Return the last count.
Complexity
O(mn) time and O(n) space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.