동적계획법

메모리를 더 사용하여 이미 접근했던 배열을 추가 접근하지 않는 방식.

 

하향식 접근법

재귀에서 많이 사용 됨.

dp 를 사용하는 알고리즘 이항 계수 ( 5 개 중 2 개 뽑는 경우의 수는?) 보통 이항 계수를 재귀로 푸는데 그러면 재귀 호출이 너무 많아진다.

이를 방지하기 위해 메모이제이션이라는 방식을 이용한다.

배열에 호출된 특정 방식에 대한 결과 값을 저장하여, 해당 특정 방식이 반복되어 호출 될 경우에 배열에 저장한 값을 가져오는 방식이 동적 계획법이다.

 

int cache[50][50];

int Combination(int n, int r)
{
	// 기저 사례
	if (r == 0 || n == r)
	{
		return 1;
	}

	// 이미 답을 구한 적 있으면 바로 반환
	int& ret = cache[n][r];
	if (ret != -1)
		return ret;

	// 새로 답을 구해서 캐시에 저장


	return ret = Combination(n - 1, r) + Combination(n - 1, r - 1);
}

상향식 접근법

for문을 사용한다.

모든 하위 문제를 해결하면서 DP 테이블을 채우기 때문에, 호출 스택의 깊이에 대한 걱정이 없다.

 

#include <iostream>
#include <vector>

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

    std::vector<int> dp(n + 1, 0);
    dp[1] = 1;

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

    return dp[n];
}

int main() {
    int n = 10;
    std::cout << "Fibonacci(" << n << ") = " << fibonacci(n) << std::endl;
    return 0;
}