Count Stepping Pad Routes
Problem
On a row of stepping pads, from pad i you may jump forward to any pad from i + 1 to i + pads[i]. You start on pad 0.
Return the number of different routes (sequences of pads visited) that end on the last pad, modulo 10^9 + 7. Return 0 if the last pad is unreachable.
Example 1
- Input:
- pads = [2, 1, 1, 0]
- Output:
- 2
0 → 1 → 2 → 3 and 0 → 2 → 3.
Example 2
- Input:
- pads = [3, 0, 0, 0]
- Output:
- 1
Only the direct jump 0 → 3; pads 1 and 2 are dead ends.
Constraints
- 1 ≤ pads.length ≤ 1000
- 0 ≤ pads[i] ≤ 1000
Hint
Show the first hint
How many routes start on pad i and finish? Call it routes[i].
Walkthrough
How to approach it
01Clarify before coding
- Does a single pad count as one route? Yes: the empty route that is already at the end.
- Are routes compared by the pads visited? Yes, two routes differ if their pad sequences differ.
- Why modulo? With every range at 1000 there are 2^(n-2) routes.
02Brute force
DFS from pad 0, trying every jump and counting the times you land on the last pad.
Cost: Proportional to the number of routes: up to 2^998, infeasible.
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.
This problem is part of Pro.