Dynamic Programming - 피보나치 수열을 이용한 Tabulation, Memoization 예제

Tabulation

def fib_tab(n):
    fib_table = [0, 1, 1]
    
    for i in range(3, n + 1):
        fib_table.append(fib_table[i - 1] + fib_table[i - 2])
    
    return fib_table[n]

# 테스트
print(fib_tab(10))

Memoization

def fib_memo(n, cache):
    # 코드를 작성하세요.
    if n <= 2:
        return 1
    if n not in cache:
        cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

def fib(n):
    # n번째 피보나치 수를 담는 사전
    fib_cache = {}
    return fib_memo(n, fib_cache)

# 테스트
print(fib(10))