[알고리즘] 동적 계획법(Dynamic Programming) - 백준 2748번 피보나치 수2

반복적 풀이

Bottom-up : 작은 문제부터 차례대로 푸는 방법

def fibonacci(n):
  if n < 2:
    return n
  
  cache = [0 for _ in range(n+1)]
  cache[1] = 1
  
  for i in range(2, n+1):
    cache[i] = cache[i-1] + cache[i-2]
  return cache[n]


print(fibonacci(int(input())))

재귀적 풀이

Top-down : 큰 문제를 작은 문제로 쪼개면서 푸는 방법

def fibonacci(n):

  cache = [-1 for _ in range(n+1)]
  def iterate(n):
    if n < 2:
      return n

    if cache[n] != -1:
      return cache[n]
    
    cache[n] = iterate(n-1) + iterate(n-2)
    return cache[n]
  
  return iterate(n)


print(fibonacci(int(input())))