피보나치 수열

피보나치 수열

 

재귀를 이용한 방법

public int fibonacci(int N) {

    // f(1) = 1
    // f(2) = 2
    // 종료 조건
    if (N <= 2) {
    	return N;
    }
    
    return fibonacci(N - 1) + fibonacci(N - 2);
}

반복문을 이용한 방법

public int fibonacci(int N) {

    int a = 1, b = 2;
    
    if (N == 1) {
    	return a;
    }
    
    for (int i = 3; i <= N; i++) {
    	int temp = a + b;
        a = b;
        b = temp;
    }
    
    return b;
}

DP를 이용한 방법

public int fibonacci(int N) {
    int[] dp = new int[N+1];

    dp[1] = 1; dp[2] = 1;
    for (int i = 3; i <= N; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[N];
}