Staircase With Allowed Strides
A climber stands at the bottom (step 0) of a staircase with n steps. In one move she may climb exactly s steps for any s in the list strides.
Return the number of different ordered sequences of moves that end exactly on step n. Because the answer can be huge, return it modulo 1000000007. Standing still at step 0 counts as one way when n = 0.
Example 1
Input: n = 4, strides = [1,2] Output: 5 Explanation: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2.
Example 2
Input: n = 3, strides = [1,3] Output: 2 Explanation: 1+1+1 and 3.
Constraints
- 0 <= n <= 10^4
- 1 <= strides.length <= 10
- 1 <= strides[i] <= 100, all distinct
Hint 1
Let ways[i] be the number of sequences that end on step i.
Hint 2
ways[i] is the sum of ways[i - s] over every stride s that fits.
Good practice for: Backend Developer, Full Stack Developer, Game Developer, Data Scientist, Machine Learning Engineer, Automation Test Engineer
Run checks your code on 3 sample tests. Submit runs all 9 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.