3가지 조건

1. Problem 이 더 작은 Problem으로 쪼개질 수 있을 때
2. 이러한 쪼개진 problem의 solution들로 더 큰 큐모의 problem의 solution을 구할 수 있을 때
3. 이러한 subproblem들이 겹칠 때

마지막 3번째는 피보나치 수열을 생각하면 된다. 많은 계산을 줄일 수 있다.

피보나치 수열은 층 수가 하나 늘어날 때마다 2가 곱해지면서 총 n개의 층이 있다. 따라서 O(2^n) 의 time complexity를 가진다.

Fn = F(n-1) + F(-2)

int fibonacci(int n)
{
	if (n == 0) return 0;
	else if (n == 1) return 1;
	else
	{
		int fib = fibonacci(n - 1) + fibonacci(n - 2);
		return fib;
	}
}

이는 2^n의 time complexity를 가지게 된다.

거르는거 없이 중복 되는 것도 계속 계산해 나가는 것이다.

이를 recursive한 DP로 풀게 되면 중복을 피할 수 있는데 문제가 있다.

stack call에는 한계가 있는데, top down 방식의 프로그래밍으로는 한계가 있어서 recursion의 depth가 stack overflow 해 버린다.

bottom up 방식으로 가장 작은 problem부터 가장 큰 problem 까지 올라가면서 해결하면 좀 더 좋은 방식이 될 것이다.

vector<int> fiboarr{ 0, 1 };
int fibonacci(int n)
{
	for (int i = 0; i < 2; ++i)
	{
		if (fiboarr[i] == n)
			return fiboarr[i];
	}
	for (int i = 2; i <= n; ++i)
	{
		fiboarr.push_back(fiboarr[i - 1] + fiboarr[i - 2]);
	}
	return fiboarr[n];
}

O(n) 의 time complexity를 가지고, O(n)의 space complexity를 가진다.

이를 optimization의 관점으로 보면 space를 O(1)으로 줄이는게 가능하다.

int fibonacci(int n)
{
	if (n == 0) return 0;
	else if (n == 1) return 1;
	vector<int> vArray{ 0, 1 };

	for (int i = 0; i <= n - 2; ++i)
	{
		vArray.push_back(vArray[0] + vArray[1]);
		vArray[0] = vArray[1];
		vArray[1] = vArray[2];
		vArray.pop_back();
	}
	return vArray[1];
}