LeetCode: 62. Unique Paths

2026-03-22

A good dynamic programming exercise. Try solving it without using the combinations formula.

62. Unique Paths

62. Unique Paths

Summary

Calculate the number of unique paths the robot can take from the top-left corner to the bottom-right corner.

Approach

Dynamic programming.

The number of unique paths to cell (i, j) is the sum of the unique paths to (i - 1, j) and (i, j - 1).

Function

Initialize:

  • paths: an m * n matrix filled with zeros.
  • paths[0][0] = 1 as the starting point.

For each cell (i, j) from top-left to bottom-right: cnt = 0 If i > 0: cnt += paths[i - 1][j] If j > 0: cnt += paths[i][j - 1] paths[i][j] = cnt

Return paths[-1][-1].

Complexity

Time Complexity: O(MN). We traverse all cells once. Space Complexity: O(MN)