Fibonacci-like Sequence

Given n up to 116, compute the n-th term of the recurrence f(n) = f(n-1) + f(n-3) with f(1)=f(2)=f(3)=1.

Easy2Dynamic programmingMathImplementationNo attempts yetTime limit2sMemory limit512 MB

Description

Examples1

The Fibonacci-like sequence is defined by $f(n) = f(n-1) + f(n-3)$ , with $f(1) = f(2) = f(3) = 1$ . Its first terms are:

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...

Given a positive integer $n$ , find the $n$ -th term of the Fibonacci-like sequence.

The first line contains a positive integer $n$ ( $1 \le n \le 116$ ).

Print the $n$ -th term of the Fibonacci-like sequence.