Modified Fibonacci method implementation - dynamic programming

Question

I found this question on Hackerrank in dynamic programming:

Define a modified Fibonacci sequence as: $$t_{n+2} = t_n + t_{n+1}^2$$

Given three integers, \$t_1\$, \$t_2\$, and \$n\$, compute and print term \$t_n\$of a modified Fibonacci sequence.

Could this efficiency be improved?

t1,t2,n = map(int, raw_input().split(" "))
array =[]
array = array+[t1, t2]
for i in range(2,n):
   ele = array[i-2] + array[i-1]*array[i-1]
   array.append(ele)   
print array[n-1]

Answer 1

Making the array initialization better:

t1,t2,n = map(int, raw_input().split(" "))
array = [t1, t2]
for i in range(2,n):
   ele = array[i-2] + array[i-1]*array[i-1]
   array.append(ele)
print array[n-1]

Currently your code needs \$\mathcal{O}(n)\$ memory, because you keep all terms. It would be more efficient to just save \$t_{n-1}\$ and \$t_{n-2}\$ and update them every loop, using tuple assignment:

t1, t2, n = map(int, raw_input().split())
for _ in range(2, n):
   t1, t2 = t2 + t1**2, t1
print t2 + t1**2