Unique Paths
A robot at the top-left of an m × n grid can only move right or down. How many distinct paths reach the bottom-right corner?
Intuition
The number of ways to reach a cell equals the ways to reach the cell above plus the ways to reach the cell to its left — the only two moves that land there. Fill the grid and the answer is the bottom-right cell.
Approach
The recursive count, and why it's slow
Since the robot only moves right or down, the number of ways to reach a cell is the ways to reach the cell above it plus the ways to reach the cell to its left: paths(i,j) = paths(i-1,j) + paths(i,j-1). Written as plain recursion this is correct but exponential — the same sub-cells get recomputed over and over. The recurrence is begging to be cached.
Fill a table bottom-up instead
Every cell's answer depends only on cells above and to the left — cells we can compute first. So build a DP table and fill it in order. The base cases are the top row and left column: there's exactly one straight-line path along an edge (all rights, or all downs), so initialize them to 1. Every interior cell then becomes the sum of its top and left neighbors, each already filled.
Read off the corner
Sweep the interior with dp[i][j] = dp[i-1][j] + dp[i][j-1]; the bottom-right cell holds the total number of paths. Each of the m·n cells is computed once, so it's O(m·n) time. Since each row only needs the row above it, you can compress the table to a single rolling row for O(n) space — but the full grid is clearest to read.
Solution & live demo
Edge cases
There is exactly one path (all rights or all downs); the all-ones edge initialization yields 1.
Start equals destination, so there is one trivial path — the single cell holds 1.
Values grow fast but stay within standard integer range for the constrained sizes; the DP avoids exponential recomputation.