Dynamic Programming - Fibonacci Number

Fibonacci Number

$F(0) = 0, \ \ \ \ \ F(1)=1, \ \ \ \ \ F(n)=F(n-1) + F(n-2)$

 

---

 

Recursion

int F(int n)
{
	if(n < 2) return 1;
	return F(n-1) + F(n-2);
}

1부터 F(n) 까지의 합 만큼의 시간이 걸린다.
내부에서 이미 계산했던 함수들이 여러번 호출되기 때문.

* 개선하는 방법
1. 재귀 sol
2. 재활용 찾기 ⇒ Memoization
3. 순서정하기 ⇒ DP

 

---

 

Dynamic Programming

int FF[1000];

int F(int n)
{
	FF[0] = FF[1] = 1;
	for(i=2; i<=n; i++)
		FF[i] = FF[i-1] + FF[i-2];
	return FF[n];
}

테이블에 이미 저장되어 있는 값을 가져다 쓴다.

작은 것부터 순서대로 계산.

 

---

 

Memoization

int FF[1000];

int init() 
{
	for(i=2; i<1000; i++)
		FF[i] = -1;
	FF[0] = FF[1] = 1;
}

int F(int n)
{
	if(FF[n] != -1) return FF[n];
	FF[n] = F(n-2) + F(n-1);
	return FF[n];
}

DP 에서 순서정하기를 못했을 때 적용.

DP보단 살짝 느림.