Loading...
Loading...
Loading...
A worker climbs n steps, taking 1, 2 or 3 steps at a time. Print the number of different ways to reach step n, modulo 1000000007. Trying every sequence of moves is far too slow.
Example 1
Input
4
Output
7
Example 2
Input
10
Output
274
Try the problem first. Open one hint at a time.
The ways to reach step k are the ways to reach k - 1, k - 2 and k - 3. A plain recursion repeats the same sub-problems and grows exponentially.
Compute the ways for 1, 2, 3, ... in order, keeping only the last three values.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor