[Python] DP 다이나믹 프로그래밍

다이나믹 프로그래밍은 전형적으로 보텀업 방식 형태를 보인다. 그렇지만 탑다운 방식과 보텀업 방식의 차이를 알아볼 필요가 있다. 상향식, 하향식에 따라 재귀호출인지 반복호출인지의 차이도 보여지기 때문이다. 

 

1. 탑다운 방식 (Top-down) 

재귀 함수를 이용하여 DP를 작성하는 방법. 큰 문제를 해결하기 위해 작은 문제를 호출한다. 

d = [0] * 100

def fibo(x):
    print('f(' + str(x) + ')', end=' ')
    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]

* 실행 결과

f(10)을 구하기 위해서 현재 10보다 작은 함수를 실행시켜서 해결하고 있다.(점점아래로 내려간다)

 

2. 바텀업 방식 (Bottom-Up)

단순히 반복문을 이용하여 푼다. 작은문제부터 차근차근 위로 올라가 큰 문제를 해결하는 방식이다. 

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

print(d[n])

* 실행 결과

55