피보나치 DP

DP_fibonacci.py

def fibo_bottom_up(n):
    d = [0] * (n+1)
    d[0] = 0
    d[1] = 1
    for i in range(2, n+1):
        d[i] = d[i-1] + d[i-2]
    return d[n]


def fibo(n):
    if n <= 1:
        return n;
    return fibo(n-1) + fibo(n-2)


d = [0] * 100
def fibo_top_down(n):
    if n <= 1:
        return n
    if d[n] > 0:
        return d[n]
    d[n] = fibo_top_down(n-1) + fibo_top_down(n-2)
    return d[n]


print(fibo_bottom_up(10))
print(fibo_top_down(10))
print(fibo(10))