(UVa) 1646 - Edge Case

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=851&page=show_problem&problem=4521

# -*- coding: utf-8 -*-
"""
Created on Sun Oct 22 14:30:38 2017

@author: Anan
"""

max_len = 10006

ls = []
ls1 = []
ls2 = []
ls3 = []
for i in range(max_len) :
    ls.append(0)
    ls1.append(0)
    ls2.append(0)
    ls3.append(0)

dp=[[ls,ls1],[ls2,ls3]]

dp[0][0][1] = 1
dp[1][1][1] = 1
  
for i in range(2,max_len) :
    dp[0][0][i] = dp[0][0][i-1] + dp[0][1][i-1]
    dp[0][1][i] = dp[0][0][i-1]
    dp[1][0][i] = dp[1][0][i-1] + dp[1][1][i-1]
    dp[1][1][i] = dp[1][0][i-1]

import sys

for i in sys.stdin :
    ii = int(i)
    print(dp[0][0][ii] + dp[0][1][ii] + dp[1][0][ii])