동적 계획법(Dynamic Programming)

큰 문제를 작은 문제로 나눠서, 중복되는 계산을 피하기 위해 결과를 저장해두고 사용하는 기법입니다.

• 사용 조건 1 : Overlapping Subproblems
  동일한 작은 문제들이 반복하여 나타나는 경우

• 사용 조건 2 : Optimal Substructure
  큰 문제의 최적해가 작은 문제의 최적해로부터 구성되는 경우

구현 방법 2가지

1. Top-Down (Memoization)

위에서부터 바로 호출을 시작하여 결과 값을 재귀를 통해 전이시켜 재활용하는 방식입니다.
재귀함수 내부에서 dp[] 배열을 사용해 결과를 저장

<예시 : 피보나치 수열>

vector<int> dp(100);

int fibonacci(int n) {
	if (n <= 2) return 1;

	if (n > dp.size()) dp.resize(n + 1);

	if (dp[n] != 0) return dp[n];
	
	return dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

2. Bottom-Up (Tabulation)

아래에서부터 계산을 수행하고 누적시켜서 큰 문제를 해결하는 방식입니다.
반복문을 이용해서 작은 문제부터 dp[] 배열을 채워나감

<예시 : 피보나치 수열>

int fibonacci(int n) {
	if (n <= 2) return 1;
	
	vector<int> dp(n + 1);
	dp[1] = 1;
	dp[2] = 1;

	for (int i = 3; i < n + 1; ++i) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}

	return dp[n];
}