[백준 10870] 피보나치 수 5

 

n이 최대 20이라 문제에 나와있는 점화식을 가지고 재귀하여 풀면 된다.

 

나는 굳이 탑다운 방식으로 풀었다.

 

public class Main {
    
    static int dp[];
    
    public static int f(int k) {
        if(k == 0) return 0;
        if(k == 1) return 1;
        if(dp[k] != -1) return dp[k];
        
        int ret = f(k-1) + f(k-2);
        dp[k] = ret;
        return ret;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        dp = new int[n+1];
        Arrays.fill(dp, -1);
        
        System.out.println(f(n));
    }
}