Custom Stride Stairs

Medium1-D Dynamic Programming

Problem

A robot climbs a staircase of n steps. Its legs allow a fixed set of stride lengths, given as the distinct positive integers in strides; each move climbs exactly one of those lengths.

Return the number of distinct ordered move sequences that end exactly on step n, modulo 1,000,000,007.

Example 1

Input:
n = 4, strides = [1, 2]
Output:
5

1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.

Example 2

Input:
n = 5, strides = [1, 3]
Output:
4

1+1+1+1+1, 1+1+3, 1+3+1 and 3+1+1.

Example 3

Input:
n = 3, strides = [2]
Output:
0

Even strides can never land on step 3.

Constraints

  • 1 ≤ n ≤ 10^4
  • 1 ≤ strides.length ≤ 20
  • 1 ≤ strides[i] ≤ 100, all distinct

Hint

Show the first hint

Generalise the two-stride staircase: what can the last move of a sequence ending on step i be?

Walkthrough

How to approach it

01Clarify before coding

  • Does order matter? Yes, 1+3 and 3+1 are different sequences.
  • Can the answer be zero? Yes, when no combination of strides lands exactly on n.
  • Why the modulo? The count grows exponentially; for n = 10^4 it has thousands of digits.

02Brute force

Recurse from step 0, trying every stride that does not overshoot, and count arrivals at n. Memoising on the current step gives the top-down DP.

Cost: Without memo the call tree has up to kⁿ leaves; with memo it is O(n·k) time and O(n) space plus a recursion depth of n, which breaks Python's default limit at n = 10^4.

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.

Solve it in the browserStart free

This problem is part of Pro.