# Online Python compiler (interpreter) to run Python online.
# Write Python 3 code in this online editor and run it.
最簡單的方法
def fib(n):
if n==0:
return 1
if n==1:
return 1
else:
return fib(n-1)+fib(n-2)
print(fib(8))
Top down
m=dict()
m[0]=1
m[1]=1
def fib(n):
if n not in m:
m[n]=fib(n-1)+fib(n-2)
return m[n]
print(fib(8))
Botton up
def fib(n):
if n==0:
return 1
if n==1:
return 1
l=[1,1]
for i in range(2,n+1):
l.append(l[i-1]+l[i-2])
return l[-1]
print(fib(8))