동적 계획법도 분할 정복처럼 문제를 더 작은 문제들로 나눈 뒤 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산.

동적 계획법과 분할 정복의 차이 : 문제를 나누는 방식. 동적 계획법에서 어떤 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기 때문에 이를 통해 속도 향상 가능. 이를 위해서는 이미 계산한 값을 저장해 두는 캐시 메모리 사용이 필요.

동적 계획법 정리 : 문제를 부분 문제로 나누고, 이를 계산해서 나온 값을 캐시에 저장하고, 이를 활용하여 중복되는 부분 문제를 해결.

가장 대표적인 예시가 이항 계수 계산.

(n, r)은 n개 중에 순서없이 r개를 골라내는 것

다음 점화식이 성립한다.

(n, r) = (n-1, r-1) + (n-1, r)

이를 사용하여 코드를 짜면

int bino(int n, int r)
{
	//기저 사례: n=r (모든 원소를 다 고르는 경우) 혹은 r=0 (고를 원소가 없는 경우)
	if(r == 0 || n == r) return 1;
	return bino(n-1, r-1) + bino(n-1, r);
}

근데 이는 중복되는 경우들이 있음. 중복은 n과 r이 커질 수록 기하급수적으로 증가함.

캐시 배열을 저장해서 사용해주면 빠른 계산 가능.

// -1로 초기화해 둔다.
int cache[30][30];
int bino2(int n, int r)
{
	// 기저 사례
	if(r == 0 || n == r) return 1;
	// -1이 아니라면 한 번 계산했던 값이니 곧장 반환
	if(cache[n][r] != -1) return cache[n][r];
	// 직접 계산한 뒤 배열에 저장
	return cache[n][r] = bino2(n-1, r-1) + bino(n-1, r);