Courier Routes Across the Grid
Easy2-D Dynamic ProgrammingFree
Problem
A delivery robot starts in the top-left cell of a warehouse floor laid out as a grid of rows × cols cells. It must reach the bottom-right cell, and on every move it goes either one cell right or one cell down.
Return the number of different routes the robot can take.
Example 1
- Input:
- rows = 3, cols = 4
- Output:
- 10
Every route is 2 downs and 3 rights in some order: choosing where the 2 downs go among 5 moves gives C(5, 2) = 10.
Example 2
- Input:
- rows = 2, cols = 2
- Output:
- 2
Right then down, or down then right.
Constraints
- 1 ≤ rows, cols ≤ 16
- The answer fits in a 32-bit signed integer.
Hint
Show the first hint
The last move into any cell came either from the cell above or from the cell to its left.
Walkthrough
How to approach it
01Clarify before coding
- Are diagonal moves allowed? No, only right and down, so every route has exactly rows - 1 downs and cols - 1 rights.
- Is a 1 × 1 floor valid? Yes: the robot is already there, which counts as one route (the empty one).
- Could the count overflow? Not within the limits: 16 × 16 gives 155,117,520.
02Brute force
Recursively try both moves from every cell and count the calls that land on the target.
Cost: O(2^(rows + cols)) time: the same sub-grid is re-explored again and again (about 10^9 leaves for 16 × 16), O(rows + cols) stack.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.