Recurrent sequence task

Question

Given the sequence f0, f1, f2, ... given by the recurrence relations f0 = 0, f1 = 1, f2 = 2 and fk = f (k-1) + f (k-3)

Write a program that calculates the n elements of this sequence with the numbers k1, k2, ..., kn.

Input format

The first line of the input contains an integer n (1 <= n <= 1000) The second line contains n non-negative integers ki (0 <= ki <= 16000), separated by spaces.

Output format

Output space-separated values ​​for fk1, fk2, ... fkn.

Memory Limit: 10MB

Time limit: 1 second

The problem is that the recursive function at large values ​​goes beyond the limit.

def f (a):
    if a <= 2:
        return a
    return f (a - 1) + f (a - 3)


n = int (input ())
nums = list (map (int, input (). split ()))
for i in range (len (nums)):
    if i <len (nums) - 1:
        print (f (nums [i]), end = '')
    else:
        print (f (nums [i]))

I also tried to solve through a cycle, but the task does not go through time (1 second):

fk1 = 0
fk2 = 0
fk3 = 0
n = int (input ())
nums = list (map (int, input (). split ()))
a = []
for i in range (len (nums)):
    itog = 0
    for j in range (1, nums [i] + 1):
        if j <= 2:
            itog = j
        else:
            if j == 3:
                itog = 0 + 2
                fk1 = itog
                fk2 = 2
                fk3 = 1
            else:
                itog = fk1 + fk3
                fk1, fk2, fk3 = itog, fk1, fk2
    if i <len (nums) - 1:
        print (itog, end = '')
    else:
        print (itog)

How else can you solve this problem so that it is optimal in time and memory?

Answer 1

First, you have to sort the numbers. Then calculate values of the sequence one by one:

while True:
    a3 = a2 + a0
    a0 = a3 + a1
    a1 = a0 + a2
    a2 = a1 + a3

Lastly, return values in beginning order. To do that you have to remember position of every number. From [45, 22, 14, 33] make [[45,0], [22,1], [14,2], [33,3]] and then sort, calculate values and change them with argument [[f45,0], [f22,1], [f14,2], [f33,3]], then sort by second value.