🏵️ 다이나믹 프로그래밍

🏵️ 다이나믹 프로그래밍

• 큰 문제를 작은 문제로 나눌 수 있고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘
• 다이나믹 프로그래밍 시간복잡도 : O(N)
• Top-Down

  d = [0]*100
  
  def fibo(x):
    if x == 1 or x == 2:
      return 1
    if d[x] != 0:
      return d[x]
    d[x] = fibo(x-1) + fibo(x-2) 
    return d[x]
  
  print(fibo(99))

• Bottom-Up

  d = [0]*100
  
  d[1] = 1
  d[2] = 1
  n = 99
  
  for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]
  
  print(d[n])