DP

동적 프로그래밍에는 두 가지 접근 방법이 있습니다.

두 접근 방법의 공통점은 다음과 같습니다.

반복되는 계산을 줄이고, 하위 문제들을 위한 해결 방안을 메모리에 저장

1. Top-down 접근법

1. 하위 문제에 대해 이미 해결되었는지를 확인한다.
   2.1 이미 해결되었다면, 해당 값을 리턴하여 상위 문제를 연산한다.
   2.2 만일 해결되지 않았다면 일반적인 방법으로 하위 문제를 해결한다.

가장 하위 문제를 찾아 해당 값을 찾아 넣어주는 방법이 되겠네요
일반적으로 재귀 호출을 통한 memorize 라고 합니다.

2. Bottom-up 접근법

하위 문제를 입력 크기별로 정렬하고 가장 작은 문제부터 가장 큰 문제의 순서로 반복적으로 해결합니다.

3. 두 접근방법의 특징

1. Top-down은 하위 문제를 재귀를 이용해 한번만 더 작은 하위 문제(이전 하위 문제)를 통해 해결된다고 가정하고 코드를 구성합니다.

2. 구현 난이도는 Top-down이 일반적으로는 쉽다고 합니다.

   • 상향식은 여러 조건처리를 위해 반복 순서를 고려해야함

3. Top-down은 재귀함수이기 때문에 Bottom-up보다 느립니다.

   • 상수요소에 대한 이점이 Bottom-up 에 있습니다. ( Combination, Fibonacci 등의 변하지 않는 값들 )

4. 충분히 큰 모든 N 에 대하여 두 접근방식은 일반적으로 동일한 시간 복잡도를 가집니다.

5. Bottom-up 을 사용하면 시간 및 공간 복잡성을 더욱 최적화 할 수 있습니다. ( 반복문 내의 가지치기 )

4. 구현

앞서 말씀드린 Combination에 대해 두 가지 접근 방식에 따라 DP로 구현해 보겠습니다.

Top-down

# Top-down
import sys, time
start = time.time()
sys.setrecursionlimit(10000)
DP = [[0] * 1001 for i in range(1001)]
def combination(n, r):
	if r == 0 or r == n:
		DP[n][r] = 1
	if not DP[n][r]:
		DP[n][r] = combination(n - 1, r - 1) + combination(n - 1, r)
	return DP[n][r]

print(combination(1000, 35))
end = time.time()
print(end - start) 

# 결과 값 : 53007599712421378893801108296363791932591235151324218238066214600
# 시간 : 0.11594009399414062
	

Bottom-up

import time
start = time.time()

DP = [[0] * 1001 for i in range(1001)]
for n in range(0, 1001):
    for r in range(0, n + 1):
        if r == 0 or n == r: DP[n][r] = 1
        else:
            DP[n][r] = DP[n - 1][r - 1] + DP[n-1][r]
print(DP[1000][35])


end = time.time()
print(end - start) 

# 결과 값 : 53007599712421378893801108296363791932591235151324218238066214600
# 시간 : 0.655327320098877

출처 : https://www.enjoyalgorithms.com/blog/top-down-memoization-vs-bottom-up-tabulation