[다이나믹 프로그래밍]

다이나믹 프로그래밍 알고리즘은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘이다.

다이나믹 프로그래밍 알고리즘을 이용하면, 문제의 최적 해결 방법이 문제에 대한 최적 해결 방법으로 구성되는 문제, 즉 최적 부분 구조를 갖고 있는 문제를 풀이 할 수 있다. 최적 부분 구조를 푸는 또 다른 알고리즘은 그리디 알고리즘이다. 그리디 알고리즘은 항상 그 순간에 최적이라고 생각되는 것을 선택하면서 풀이해 나가는 것이고, 다이나믹 프로그래밍은 하위 문제들의 결과를 저장해뒀다고 풀이해 나간다는 차이가 있다. 여기서 중요한 점은 "중복된" 문제들이란 점이며, 중복되지 않은 문제들은 다이나믹 프로그래밍으로 풀리지 않는다.

[최적 부분 구조]

서울-대구-부산

서울-대구 의 최적의 길 + 대구-부산 의 최적의 부분 구조 길로 이루어 질 수 있다.

하지만 만약 서울-부산의 길이 있다면, 더이상 최적의 부분 구조가 아니다.

그리디, 디피, 분할 정복 그 어떤걸로도 풀 수 없다.

[다이나믹 프로그래밍 방법론]

상향식[타뷸레이션, Bottom-up]:

def fib(n):
	dp[0] = 0
	dp[1] = 1
	
	for i in range(2, n+1):
		dp[i] = dp[i-1] + dp[i-2]
	return dp[n]

하향식[메모이제이션, Top-Down]:

def fib(n):
	if n <= 1:
		return n
	if dp[n]:
		return dp[n]
	dp[n] = fib(n-1) + fib(n-2)
	return dp[n]

[0-1 배낭 문제 ]

def zero_one_knapsack(cargo):
	capacity = 15
	pack =[]

	for i in range(len(cargo) + 1):
		pack.append([])
		for c in range(capacity + 1):
			if i == 0 or c == 0:
				pack[i].append(0)
			#더 넣을 공간이 있다.무게 뺀거 + 지금 물건 선택한 가격, 즉 그 물건 선택 o
			elif cargo[i-1][1] <= c:
				pack[i].append(max(cargo[i-1][0] + pack[i-1][c-cargo[i-1][1]], pack[i-1][c]))
			#더 넣을 공간이 없다. 앞의 행 값 그냥 복사, 즉 그 물건 선택 x
			else:
				pack[i].append(pack[i-1][c])
	return pack[-1][-1]