Unique Paths

Problem

A robot starts at the top-left corner of an m × n grid and wants to reach the bottom-right corner. It can only move RIGHT or DOWN at each step. Return the number of distinct paths. (LeetCode 62.)

Examples

Constraints

1 ≤ m, n ≤ 100.

Attempt it first

This is the canonical grid-shaped 2D DP from this module's 2D DP Patterns concept lesson: dp[i][j] genuinely represents a real position in space, and the two indices ARE row and column, not two independent sequence counters. Before opening anything, work out: how can the robot have arrived at cell (i, j), given the only two legal moves are right and down — and what does that tell you about dp[i][j]'s dependencies?