You are at the International Monkey Bars Climbing Competition 2017! Each contestant must climb various stretches of monkey bars during each round. The rules are that you may not more move than 3 bars at a time. Find the number of distinct ways to climb a given section.
Example
For n = 4, the output should be
monkeyBars(n) = 7.
There are 7 distinct ways to climb the bars - 3 + 1, 1 + 3, 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, 1 + 1 + 1 + 1, 2 + 2.
Input/Output
- [time limit] 4000ms (py3)
[input] integer n
Number of bars.
Guaranteed constraints:
1 ≤ n ≤ 60.[output] integer64
Number of distinct ways to climb.
Solution
When investigating the series, we can see that the emerging pattern is known as the tribonacci number sequence - a generalization of fibonacci numbers. The definition is
\[T_n = T_{n-1} + T_{n-2} + T_{n-3}\]
for \(n\geq 4\) and \(T_1=T_2=1, T_3=2\). This recurrence relation can be implemented with Python like this:
def monkeyBars(n):
a = b = 1
c = 2
while n:
a, b, c = b, c, a + b + c
n-= 1
return a