[이.코.테] 다이나믹 프로그래밍

DP 사용 조건

• 큰 문제를 작은 문제로 나눌 수 있다.
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

탑다운(Top-Down) 방식

# 피보나치 수열 with 재귀 함수
d = [0] * 100

def pibo(x):
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = pibo(x-1) + pibo(x-2)
    return d[x]

 

보텀업(Bottom-Up) 방식

# 피보나치 수열 with 반복문
d = [0] * 100

d[1] = 1
d[2] = 1

for i in range(3, 99):
    d[i] = d[i-1] + d[i-2]

 

파이썬 재귀 제한 완화

import sys

sys.setrecursionlimit(10**6)

 

💡 가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식으로 구현할 것