How many ways to the corner?
A cell's count is the sum of the ways to reach the two cells that lead into it. About 12 minutes.
A delivery robot in a city of blocks
A delivery robot starts at the top-left corner of a grid of city blocks and has to reach the bottom-right corner. It only ever drives right or down. How many different routes are there?
For a 20 × 20 city there are over 35 billion routes, far too many to list. But ask the familiar question about the last move. The robot entered each corner either from the corner above it or from the corner to its left. So the routes into a corner are the routes into the one above plus the routes into the one on the left.
The edges are easy, the rest fills itself
Along the top edge there's only one route to each corner: keep driving right. Down the left edge, the same: keep driving down. So write 1 along both edges first.
Then fill the rest row by row, each box adding the box above and the box to its left. Both are always filled by the time you get there. In a 3 × 7 city, the bottom-right corner ends up at 28.
ways = [[1] * n for _ in range(m)] # first row and column: 1 way
The top row can only be reached by going right all the way, and the left column by going down. One path each.
In a 2 × 2 city, the corner above the finish has 1 route and the corner to its left has 1 route. How many routes reach the finish?
- A2
- B1
- C4
Show the answer
2. 1 + 1 = 2: right then down, or down then right.
Unique paths
A robot starts at the top-left corner of an m × n grid and can only move right or down. Return how many distinct paths lead to the bottom-right corner.
m = 3, n = 7 → 28
1 ≤ m, n ≤ 20 · return a long