#include <stdio.h>

int d[100] = { 0, };
// 값을 저장하는 저장소 메모이제이션

int dp(int x)
{
	if (x == 1) return 1;
	if (x == 2) return 1;
	// 피보나치 수열 1, 1, 2, 3, 5, ....
	// 피보나치 수열은 첫번째 두번째 값이 1 로 시작하기 때문에
	// 초기값 1, 2 를 1 로 설정하는것과 동시에 재귀함수 종료 조건이기도 합니다.

	if (d[x] != 0) return d[x];
	// 이미 구한값이 존재한다면 존재하는 값을 반환합니다.
	// 배열의 값이 0 이 아니라는것은 값이 존재한다는 것을 의미합니다.

	return d[x] = dp(x - 1) + dp(x - 2);
	// 피보나치 수열의 값을 구한전이 없다면 d[] 값을
	/*
   	 ex) dp(4) 일경우
    	 4번째 수열값을 구하려면 3번째 dp(3) 값과 2번째 dp(2) 값을 더한값이 필요하고
    	 또 3번째 dp(3) 수열을 구할때는 2번째 dp(2) 수열과 1번째 dp(1) 수열이 필요합니다.
  	*/
}

int main(void)
{
	printf("%d", dp(40));

	system("pause");
	return 0;
}