fibonacchi.py

#/usr/bin/python

# 動的計画法サンプル
# http://www.slideshare.net/iwiwi/ss-3578511

done = [False] * 100
memo = [0] * 100

def fib(num):
    global done
    global memo

    if num == 0: return 0
    if num == 1: return 1

    if done[num - 1]: return memo[num - 1]

    done[num - 1] = True
    memo[num - 1] = fib(num - 1) + fib(num  - 2)
    return memo[num - 1]

print(fib(100))
print(fib(50))
print(fib(40))