Ch 09 Recursion and Dynamic Programming

Ch 09 Recursion and Dynamic Programming

---

재귀적 방법

• 상향식과 하향식으로 나눠 진다.

동적 프로그래밍의 예: 피보나치 수
중간과정을 저장하면 그게 동적 프로그래밍이다.

$n^2$ 복잡도의 일반 코드

int fibonacci(int i){
	if(i==0) return 0;
	if(i==1) return 1;
	return fibonacci(i-1) + fibonacci(i-2);
}

Time complexity를 $O(n)$으로 줄이는 코드

int[] fib = new int[max];
int fibonacci(int i){
	if (i==0) return 0;
	if (i==1) return 1;
	if (fib[i] != 0) return fib[i]; // 캐시된 결과 반환
	fib[i] = fibonacci(i-1) + fibonacci(i-2); // 계산 결과 캐시
	return fib[i];
}

동적 프로그래밍을 구현 할 때의 전략은 다음과 같다.

• 재귀함수를 먼저 구현
• 캐쉬 부분을 구현