2-D Dynamic Programming

LeetCode 62

LeetCode #62Difficulty: MediumNeetCode 150

LeetCode 62: Unique Paths

LeetCode

A robot is located at the top-left corner of a m x n grid. How many possible unique paths to reach bottom-right?

Problem Description

There is a robot on an `m x n` grid. The robot is initially located at the top-left corner and wants to reach the bottom-right corner. The robot can only move either down or right at any point in time.

Examples:
Input: m = 3, n = 7
Output: 28
Constraints:
  • 1 <= m, n <= 100

Core Mental Model

Any cell (r, c) can only be entered from the cell above (r-1, c) or the cell to the left (r, c-1). Therefore: Paths(r, c) = Paths(r-1, c) + Paths(r, c-1).

Formal Loop Invariant

Invariant: Cell (r, c) holds the sum of paths from all valid preceding cells.

Key Architectural Takeaway:

2D grid DP where transitions depend only on the previous row can be compressed into a single 1D array.

Asymptotic Complexity Analysis

Time ComplexityO(M * N)Linear scan
Space ComplexityO(N) with 1D row buffer.Constant auxiliary

Bottleneck: Grid cell iteration.

Edge Cases & Screener Traps

  • m = 1 or n = 1 (only 1 straight path)