피보나치 수열

1. n >= 2인 자연수
   F(n) = F(n-1) + F(n-2)
2. n == 0
   F(0) = 0
3. n == 1
   F(1) = 1

코드

재귀로 푸는 피보나치 수열

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

반복문으로 푸는 피보나치 수열

def fib_iteration(n):
  a, b = 0, 1
  for _ in range(n):
    a, b = b, a+b
  return a

메모이제이션으로 푸는 피보나치 수열(top-down)

def fib_memoization(n, memo={}):
  if n in memo:
    return memo[n]
  
  if n <= 1:
    return n
    
  memo[n] = fib_memoization(n-1, memo) + fib_memoization(n-2, memo)
  
  return memo[n]

DP 테이블로 푸는 피보나치 수열(down-up)

def fib_dp(n):
  if n <= 1:
    return n
  dp = [0] *(n+1)
  dp[1] = 1
  
  for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]
  
  return dp[n]