optimal substructure - 피보나치 수

피보나치 수를 구하다 보면

겹치는 호출이 생기게 된다

이럴땐 다음과 같이 메모하여 저장해 줄 수 있다.

int memo[100];
 
 
int fibonacci(int n){
 
    if (n <= 1){
 
    return n;
 
    } else {
 
        if(momo[n]>0){
 
            return memo[n];
 
        }
 
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
 
    return memo[n]
 
    }
 
}