[SWEA][S/W 문제해결 응용] 피보나치 수

풀이

import java.util.*;
 
public class Main {
    static int[] memo;
    static int[] f;
    
    //메모이제이션X
    static int fibo(int n) {
        if(n<2)
            return n;
        return fibo(n-1)+fibo(n-2);
    }
    
    //메모이제이션O
    static int fibo_memo(int n) {
        if(n > 2 && memo[n]==0)
            memo[n] = fibo_memo(n-1)+fibo_memo(n-2);
        return memo[n];
    }
 
    //동적계획법
    static int fibo_dp(int n) {
        for(int i=2;i<=n;i++)
            f[i] = f[i-1]+f[i-2];
        return f[n];
    }
    
    public static void main(String[] args) {
        int n = 5;
        //저장 배열 생성
        memo = new int[n+1];
        f = new int[n+1];
        //저장 배열 초기화(첫 번째와 두 번째 피보나치 수 초기화)
        memo[1] = 1;
        memo[2] = 1;
        
        f[1] = 1;
        f[2] = 1;
        
        //피보나치 구하기
        System.out.println(fibo(n));
        System.out.println(fibo_memo(n));
        System.out.println(fibo_dp(n));
    }
}