재귀, memoization, DP

피보나치를 예시로 설명

재귀

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

memoization (append, pop 사용)

def fibo(n):
    if n >= 2 and len(arr) <= n:
        arr.append(fibo(n - 1) + fibo(n - 2))
    return arr[n]

arr = [0, 1]
print(fibo(10))  # => 55 
print(arr)  # => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

memoization (append, pop 사용안하고)

def fibo(n):
    if n >= 2 and arr[n] == 0:
        arr[n] = fibo(n - 1) + fibo(n - 2)
    return arr[n]

n = 10
arr = [0] * (n + 1)
arr[0] = 0
arr[1] = 1
print(fibo(10))  # => 55 
print(arr)  # => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

DP

n = 10
arr = [0] * (n + 1)
arr[0] = 0
arr[1] = 1
for i in range(2, n + 1):
    arr[i] = arr[i - 1] + arr[i - 2]
print(arr[n])  # => 55 
print(arr)  # => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]