[C++] 백준 2747번 피보나치 수

다이나믹 프로그래밍으로 문제를 풀었습니다.

점화식은 다음과 같습니다.

DP[i] = DP[i - 1] + DP[i - 2];

현재 위치의 값은 이전과, 그 이전의 값을 더한 값입니다.
이를 반복해서 n의 위치에 피보나치 수를 구할 수 있습니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int main(int argc, char *argv[])
{
	int n;
	long long DP[45];

	cin >> n;

	DP[0] = 0;
	DP[1] = 1;

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

	cout << DP[n] << endl;

	return 0;
}