다이나믹 프로그래밍 DP 동적계획법

- 하나의 문제는 단 한번만 풀도록 하는 알고리즘

- 이미 해결한 문제를 반복 계산하는 것을 막아 효율적으로 만드는 것

- 한번 계산한 결과를 "메모이제이션"을 활용해서 배열에 저장

 

#include <iostream>
using namespace std;

int d[100];

int fibonacci(int x) {
	if (x == 1) return 1;
	if (x == 2) return 1;
	if (d[x] != 0) return d[x];
	return d[x] = fibonacci(x - 1) + fibonacci(x - 2);
}

int main(void) {
	cout << fibonacci(3) << endl;
}