피보나치 수열

재귀(recursive)와 DP의 대표적인 문제

피보나치 수열

• 앞에 두 개의 수를 더한 것이 다음 수의 답이 되는 수열이다.

• f(0) = 0

• f(1) = 1

• f(N + 2) = f(N + 1) + f(N)

• 초깃값과 점화식이 존재하는 수열이다.

// top-down
public static int top_down(int N) {
    if (N == 1 || N == 2) return 1;
    return top_down(N - 1) + top_down(N - 2);
}

// top-down : memoization
public static int top_down_memoization(int N) {
    if (dp[N] > 0) return dp[N];
    if (N == 1 || N == 2) return dp[N] = 1;

    return dp[N] = top_down_memoization(N - 2) + top_down_memoization(N - 1);
}

• 메모이제이션의 핵심은

  • if (dp[N] > 0) return dp[N]; 이거랑

  • return dp[N] = top_down_memoization(N - 2) + top_down_memoization(N - 1); 이거다.

// bottom-up
public static void bottom_up(int N) {
    for (int i = 3; i <= N; i++) {
        dp[i] = dp[i - 2] + dp[i - 1];
    }
}

문제 : https://www.acmicpc.net/problem/2748