[ Python ] 다이나믹 프로그래밍 ( 동적 계획법 )

다이나믹 프로그래밍

• 큰 문제를 작은 문제로 나눌 수 있다.
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일 하다.
  다음의 조건에서 큰 문제를 여러 작은 문제로 나누어 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 방법

코드

from collections import defaultdict
# 한번 계산된 결과를 메모제이션 하기 위한 딕셔녀리 초기화
memory = defaultdict(int)

# 재귀함수를 이용하여 구현한 Top-Down 방식
def fibo_topdown(x):
  if x<=2 :
    return 1
  
  if x in memory:
    return memory[x]
  
  memory[x] = fibo(x-1)+fibo(x-2)
  return memory[x]
# 반복문을 이용하여 구현한 Bottom-Up 방식
def fibo_bottomup(x):
  memory[1] = 1
  memory[2] = 1

  for num in range(3,x+1):
    memory[num] = memory[num-1]+memory[num-2]