Unique Paths

Problem

There is a robot on an m x n grid. The robot is initially located at the top-left corner. The robot can only move either down or right at any point in time. Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Examples

The brute-force approach

Recursively count paths: from cell (r, c), you can go right to (r, c+1) or down to (r+1, c). Base case: if you're in the last row or last column, there's exactly 1 path (you can only go straight to the destination).

def paths(r, c):
    if r == m - 1 or c == n - 1:
        return 1           # only one direction left
    return paths(r+1, c) + paths(r, c+1)
return paths(0, 0)

O(2^(m+n)) without memoization — each call branches into two, and the same sub-grids are recomputed many times.

Spotting the pattern

This is a Dynamic Programming problem. The key question to ask yourself:

How many ways can you reach a cell in the first row? In the first column? Use that as your base case.

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.