Unique Paths
A robot starts at the top-left of an m × n grid and can only move right or down. How many unique paths reach the bottom-right?
A way to picture it
A delivery robot in a city of one-way streets can only drive east or south. The number of routes to any intersection is the routes arriving from the north plus the routes arriving from the west.
How to approach it
paths[r][c] = paths[r − 1][c] + paths[r][c − 1]. The top row and left column are all 1s.
Example
Input: {"m":3,"n":7}. Output: 28.
Complexity: O(m · n) time and O(n) space. One cell at a time; a single rolling row is enough.
This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.