# Codefights: monkeyBars

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