LeetCode 62 Unique Paths - Example and Complexity Analysis

Trace m = 3, n = 3.

Initialize first row and column to 1: dp = [[1,1,1], [1,,], [1,,]]

Fill remaining: dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2 dp[1][2] = dp[0][2] + dp[1][1] = 1 + 2 = 3 dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3 dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6

Answer: $6$ paths in a $3 \times 3$ grid.

$O(m \times n)$ time. $O(n)$ space if using 1D rolling array.