Problem:
 Score : 200 points    Problem Statement It is November 18 now in Japan. By the way, 11 and 18 are adjacent Lucas numbers.  You are given an integer N . Find the N -th Lucas number.  Here, the i -th Lucas number L_i is defined as follows:   L_0=2  L_1=1  L_i=L_{i-1}+L_{i-2} (i≥2)       Constraints  1≤N≤86  It is guaranteed that the answer is less than 10^{18} .  N is an integer.         Input Input is given from Standard Input in the following format:  N       Output Print the N -th Lucas number.        Sample Input 1 5      Sample Output 1 11   L_0=2  L_1=1  L_2=L_0+L_1=3  L_3=L_1+L_2=4  L_4=L_2+L_3=7  L_5=L_3+L_4=11   Thus, the 5 -th Lucas number is 11 .       Sample Input 2 86      Sample Output 2 939587134549734843

Solution (Python):
def luca(n):
    if lucas[n] != 0:
        return lucas[n]
    else:
        lucas[n] = luca(n-1) + luca(n-2)
        return lucas[n]

n = int(input())

lucas = [0 for x in range(n+1)]
lucas[0] = 2
lucas[1] = 1

if n >= 2:
    print(luca(n))
else:
    print(luca(n))

Solution (Python):
n=int(input())

a=[]
a.append(2)
a.append(1)

if n==1:
    print(1)
elif n==2:
    print(3) 
else:    
    for i in range(n-1):
        a.append(a[0]+a[1])
        del a[0]
    print(a[1])

Solution (Python):


N = int(input())

L = [0 for i in range(N+1)]

L[0] = 2
L[1] = 1

for i in range(2, N+1):
    L[i] = L[i-1] + L[i-2]

print(L[N])

Solution (Python):
def main():
	n = int(input())

	dp=[0 for i in range(n+1)]
	dp[0]=2
	dp[1]=1
	for i in range(2,n+1):
		dp[i] = dp[i-1]+dp[i-2]
	print(dp[n])
	
if __name__ == "__main__": main()

Solution (Python):

n = int(input())
l0 = 2
l1 = 1

for i in range(1, n):
    tmp = l1
    l1 += l0
    l0 = tmp
print(l1)

Solution (Python):
N = int(input())
a = 2
b = 1
if N == 1:
    print(b)
else:
    for i in range(1, N):
        c = a + b
        a = b
        b = c
    print(c)

Solution (Python):



n = raw_input()
n = int(n)

b2 = 2
b1 = 1

if n == 1:
    a = 1
else:
    for i in range(n-1):
        a = b1 + b2
        b2 = b1
        b1 = a
        

print a

Solution (Python):
n = int(raw_input())

l = [2,1]

if n==0:
  print "2"
  exit(0)
if n==1:
  print "1"
  exit(0)

for a in range(1,n):
  l.append( l[a] + l[a-1] )

print l[-1]

Solution (Python):
a=int(input())
l0=2
l1=1

if a==1:
  print(1)
else:
    for i in range(a-1):
        l2 = l1 + l0
        l0 = l1 
        l1 = l2
    print(l2)

Solution (Python):
n=int(input())

num=[2,1]

for i in range(n-1):
    num.append(num[-1]+num[-2])
print(num[n])

Solution (Python):
n = int(input())
a = [None for i in range(87)]
a[0] = 2
a[1] = 1

def calc(N):
    if a[N]:
        return a[N]
    elif a[N-1] and a[N-2]:
        a[N] = a[N-1] + a[N-2]
        return a[N]
    else:
        a[N] = calc(N-1) + calc(N-2)
        return a[N]

print (calc(n))

Solution (Python):
N = int(input())
L = [2, 1]
if N == 1:
    print(1)
else:
    for i in range(N-1):
        L.append(L[-1] + L[-2])
    print(L[-1])

Solution (Python):
n = int(input())
l = [2, 1]
for i in range(2, n+1):
    l.append(l[i-1] + l[i-2])
print(l[-1])

Solution (Python):



def main():
    N = int(input())
    if N == 1:
        return 1
    else:
        lucas = []
        lucas.append(2)
        lucas.append(1)
        for i in range(1, N):
            lucas.append(lucas[-1]+lucas[-2])
        return lucas[-1]

if __name__ == "__main__":
    print(main())

Solution (Python):
N = int(input())
a, b, c = 2, 1, 3
for i in range(N):
    a, b, c = b, c, b + c
print(a)

Solution (Python):

N = int(input())
memo = [-1 for _ in range(N+1)]
def lucas(N):
    global memo
    if N==0:
        memo[0] = 2
        return 2
    if N==1:
        memo[1] = 1
        return 1
    if(memo[N]>0):
        return memo[N]
    else:
        memo[N] = lucas(N-1) + lucas(N-2)
        return memo[N]


print(lucas(N))

Solution (Python):
n = int(input())
l = []
l.append(2)
l.append(1)
if n == 1:
	print(1)
else:
	for i in range(2,n+1):
		li = l[i-2] + l[i-1]
		l.append(li)
	print(li)

Solution (Python):
dp = [-1]*87

def func(n):

    if dp[n] != -1:
        return dp[n]

    dp[n] = func(n-1) + func(n-2)
    return dp[n]


dp[0] = 2
dp[1] = 1

num = int(input())
print(func(num))

Solution (Python):
N = int(input())

L = [0 for i in range(87)]
L[0] = 2
L[1] = 1

if N == 1:
    print(1)
else:
    for i in range(2, N + 1):
        L[i] = L[i-1] + L[i-2]
    print(L[N])

Solution (Python):



n = int(input())

lucas_nr = [2, 1]
for i in range(2, n + 1):
    lucas_nr_i = lucas_nr[-1] + lucas_nr [-2]
    lucas_nr.append(lucas_nr_i)
print(lucas_nr[-1])

Solution (Python):
def main():
    N = int(input())
    
    L = [2, 1]
    for x in range(N - 1):
        L.append(L[x] + L[x + 1])

    print(L[-1])


if __name__ == "__main__":
    main()

Solution (Python):
import sys

N = int(sys.stdin.readline().strip())

def L(i, cache={}):
    if i == 0:
        return 2
    if i == 1:
        return 1
    if i >= 2:
        if i in cache:
            return cache[i]
        r = L(i-2) + L(i-1)
        cache[i] = r
        return r

print(L(N))

Solution (Python):
N = int(input())

Ls = [0] * (N + 1)
Ls[0] = 2
Ls[1] = 1
for i in range(2, N + 1):
    Ls[i] = Ls[i - 1] + Ls[i - 2]

print(Ls[N])

Solution (Python):
luca = [2,1]
for i in range(2,100):
    luca.append(luca[i-2] + luca[i-1])
print(luca[int(input())])

Solution (Python):
N = int(input())
L = [None] * 100
L[0] = 2
L[1] = 1

for i in range(2, N + 1):
    L[i] = L[i - 2] + L[i - 1]

print(L[N])

Solution (Python):
num = int(input())
L = [2, 1]
for i in range(2, num + 1):
    l = L[i - 2] + L[i - 1]
    L.append(l)
print(L[-1])

Solution (Python):
from functools import lru_cache
@lru_cache(maxsize=1000)
def Lucas(N):
    if N == 0:
        return 2
    elif N == 1:
        return 1
    else:
        return Lucas(N-1) + Lucas(N-2)
N = int(input())
print(Lucas(N))

Solution (Python):


n = int(input())

l = [0 for i in range(100)]
l[0] = 2
l[1] = 1

if(n==1):
    print(1)
else:
    for i in range(2,n+1):
        l[i] = l[i-1]+l[i-2]
    print(l[n])

Solution (Python):
N = int(input()) + 1

memo = [0] * N
for i in range(N):
  if i == 0:
    memo[i] = 2
  elif i == 1:
    memo[i] = 1
  else:
    memo[i] = memo[i-1] + memo[i-2]

print(memo[N-1])

Solution (Python):
N = int(input())
luka = [2,1]

for i in range(2,N+1):
    luka.append(luka[i-1]+luka[i-2])

print(luka[N])

Solution (Python):
n = int(input())
a, b = 2, 1
for _ in range(n):
   a, b = b, a+b
print(a)

Solution (Python):
n = int(input())
a = 2
b = 1
for i in range(1, n):
    a, b = b, a + b
print(b)

Solution (Python):
import functools

memo = {}

def L(i):
    if i==0:
        return 2
    if i==1:
        return 1
    if i in memo:
        return memo[i]
    memo[i] =  L(i-1)+L(i-2)
    return  memo[i]

for i in range(100):
    (L(i))

print(L(int(input())))

Solution (Python):
N=int(raw_input())
l1, l2 = 1, 2
for n in range(N-1):
  l1, l2 = l1+l2, l1
print l1

Solution (Python):
n = int(input())

l = [2, 1]
for _ in range(n - 1):
    l.append(l[-2] + l[-1])
print(l[-1])

Solution (Python):
d = {0: 2, 1: 1}
def l(n):
    if n in d:
        return d[n]
    r = d[n] = l(n-1) + l(n-2)
    return r
print(l(int(input())))

Solution (Python):
lucas = {}

def luca(i):
    global lucas
    if i in lucas:
        return lucas[i]
    elif i == 0:
        ret = 2
    elif i == 1:
        ret = 1
    else:
        ret = luca(i-2) + luca(i-1)
    lucas[i] = ret
    return ret

N = int(input())

print(luca(N))

Solution (Python):
def solve(n):
    if cache[n] > 0:
        return cache[n]
    ret = cache[n] = solve(n - 1) + solve(n - 2)
    return ret


cache = [0] * 87
cache[0] = 2
cache[1] = 1
print(solve(int(input())))

Solution (Python):
L = [2, 1]
for i in range(85):
  L.append(L[-1] + L[-2])
 
n = input()
print L[n]

Solution (Python):




l=[0]*100
l[0]=2
l[1]=1
for i in range(2,100):
    l[i]=l[i-1]+l[i-2]
print(l[int(input())])

Solution (Python):
memo = {}


def L(n):
    if n in memo:
        return memo[n]
    if n == 0:
        return 2
    if n == 1:
        return 1
    memo[n] = L(n - 1) + L(n - 2)
    return memo[n]

print(L(int(input())))

Solution (Python):
from sys import stdin
a = [2,1]
for i in xrange(100):
 a.append(a[-1] + a[-2])
print a[int(stdin.readline())]

Solution (Python):
N = int(input())
l = [2, 1]
for i in range(90):
    l.append(l[-1] + l[-2])
print(l[N])

Solution (Python):


import functools


@functools.lru_cache(maxsize=None)
def lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    else:
        return lucas(n - 1) + lucas(n - 2)


def main():
    n = int(input())
    print(lucas(n))


if __name__ == '__main__':
    main()

Solution (Python):
n = int(raw_input())
l = [0]*100
l[0] = 2
l[1] = 1
for i in xrange(2,100):
    l[i] = l[i-1] + l[i-2]
print l[n]

Solution (Python):
l = [2, 1]
for x in xrange(2, 87):
    l.append(l[x - 2] + l[x - 1])
print l[input()]

Solution (Python):

N = int(input())

l0 = 2
l1 = 1

for _ in range(N - 1):
    l0, l1 = l1, l0 + l1

print(l1)

Solution (Python):
L = [2, 1]
for i in range(100):
	L.append(L[-1] + L[-2])
print L[input()]

Solution (Python):
L = [2, 1]
for i in range(100):
  L += [L[-2]+L[-1]]
print L[input()]

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()
x = []
for i in range(n+1):
    if i == 0:
        x.append(2)
    if i == 1:
        x.append(1)
    if i >= 2:
        x.append(x[-2] + x[-1])
print(x[-1])

Solution (Python):
N = int(input())
a = [0] * 100
a[0] = 2
a[1] = 1
for i in range(2, 100):
    a[i] = a[i-1] + a[i-2]
print(a[N])

Solution (Python):
n = int(input())
l = [0] * 228
l[0] = 2
l[1] = 1
for i in range(2, 228):
    l[i] = l[i - 1] + l[i - 2]
print(l[n])