[백준] 1003번 - 동적 계획법

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

위는 n번째 피보나치 수를 구하는 함수이다. 

이렇게 재귀호출을 이용하면 6번째 피보나치 수를 구하는 걸 예시로 들었을 때

fibo(6)은 fibo(4)와 fibo(5)를 호출하고 fibo(5)는 fibo(3)과 fibo(4)를 호출하는 과정을 반복하게 되는데

이 과정에서 fibo(4)는 2번 호출되고 밑으로 내려갈 수록 같은 계산이 여러번 이루어지게 된다. 

 

그래서 동적 계획법은 불필요한 동일 연산을 줄이기 위해 한번 계산한 함수의 값을 저장한다.

 

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

 

위 코드처럼 fibo배열에 피보나치 수를 연산한 것을 저장하면 한번 계산한 fibo(3),fibo(4),fibo(5)... 등은 

다시 계산할 필요가 없다.