Unique Paths

Problem

Robotic warehouse systems plan delivery routes on grid floors where vehicles can only move forward or downward to minimize backtracking. A robot starts at the top-left corner of an m x n grid and can only move right or down. Count the number of distinct paths to reach the bottom-right corner.

Input: m=3, n=7  → 28
Input: m=3, n=2  → 3
Input: m=1, n=1  → 1

Verification

Trace a 3x3 grid: after initialization all edges are 1. dp[1][1]=1+1=2, dp[1][2]=1+2=3, dp[2][1]=1+2=3, dp[2][2]=3+3=6. Verify: C(4,2)=6 paths from (0,0) to (2,2).

Solution

Approach: 2D grid DP summing the two incoming directions.

Define dp[row][col] as the number of distinct paths from the top-left corner to that cell. Since the robot moves only right or down, the only ways to arrive at an interior cell are from the cell directly above or the cell directly to the left, and those two path sets are disjoint. So dp[row][col] = dp[row-1][col] + dp[row][col-1]. The base cases are the top row and left column: there is exactly one straight-line path to any boundary cell (all right-moves along row 0, all down-moves down column 0). Initializing the whole grid to 1 seeds those edges for free, and the nested loops starting at index 1 overwrite only the interior cells, where both neighbors already hold final counts. The answer lands in dp[m-1][n-1]. Trace a 3x3 grid: the edges are all 1, then dp[1][1]=2, dp[1][2]=3, dp[2][1]=3, and dp[2][2]=6, matching the closed form C(m+n-2, m-1) = C(4,2) = 6.

Edge cases: A 1x1 grid is already at the goal - the loops never run and dp[0][0] stays 1. Single-row or single-column grids keep their initialized 1s, correctly reporting the one straight path.

Complexity: O(m x n) time, O(m x n) space - one addition per cell; reducible to a single row of size n since each cell reads only the row above and its left neighbor.