[알고리즘/C++] 다이나믹 프로그래밍

- DP, Dynamic Programming : 여러 하위 문제를 쌓아올려 주어진 문제를 해결
  - 점화식을 찾아내어 결과를 구현 Ex) 피보나치 수열

//재귀 : n번째 피보나치는 n-1과 n-2번째의 합
//O(1.618^n)
int fibo(int n){
	if(n <= 1) return 1;
    return fibo(n-1) + fibo(n-2);
}
//DP : 0, 1번째 수열부터 n번째까지의 값을 순서대로 계산
//O(n)
int fibo(int n){
	int f[20];
    f[0] = f[1] = 1;
    
    for(int i = 2 ; i <= n ; i++){
    	f[i] = f[i-1] + f[i-2];
    }
    return f[n];
}

- DP의 풀이과정
  1. 테이블 정의
  2. 점화식 찾기
  3. 초기값 정의