python 递推踩方格

n=int(input())

l=[0 for x in range(25)]

r=[0 for x in range(25)]

u=[0 for x in range(25)]

l[1]=1

r[1]=1

u[1]=1

for x in range(2,n+1):

    l[x]=l[x-1]+u[x-1]

    r[x]=r[x-1]+u[x-1]

    u[x]=l[x-1]+u[x-1]+r[x-1]

print(l[n]+r[n]+u[n])