[고급 알고리즘] Dynamic Programming: Fibonacci

1. Fibonacci (피보나치 수열)

• 직전 두 항의 합인 수열입니다. (첫째항과 둘째항은 1)

 

점화식

• $fib(n) = fib(n-1) + fib(n-2)$

 

예시: $fib(5)$

상태공간트리(Call Tree)

• $fib(4)+fib(3)$
• $(fib(3)+fib(2)) + (fib(2)+fib(1))$
• $((fib(2)+fib(1)) + (fib(1)+fib(0))) + ((fib(1)+fib(0)) + fib(1)$
• $(((fib(1)+fib(0)) + fib(1)) + (fib(1)+fib(0))) + ((fib(1)+fib(0)) + fib(1))$

 

2. 풀이

 

코드

public int fibDP(int n) {
    if (n>3 && memo[n] == NOT_UPDATED) memo[n] = fibDP(n-1) + fibDP(n-2);

    return memo[n];
}

 

3. 사례

사각형 채우기

 

토끼 번식

번식

• 조건: 두 달 이상된 토끼
• 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다.

 

n번째 달의 토끼 수는?

• 첫째 달: 1쌍만이 존재 (초기값)
• 둘째 달: 1쌍 (새끼 못낳음)
• 셋째 달: 2쌍 (1쌍+1쌍: 첫 달 토끼 1쌍이 새끼를 낳음)
• 넷째 달: 3쌍 (2쌍+1쌍: 둘째 달 토끼 1쌍이 새끼를 낳음)
• 다섯째 달:5쌍 (3쌍+2쌍: 셋째 달 토끼 2쌍이 새끼를 낳음)
• ...
• n-2번째 달: a쌍
• n-1번째 달: b쌍
• n번째 달: b+a쌍

 

출처

• Wiki - 피보나치 수