본문 바로가기

알고리즘/Algorithm

Dynamic Programing 피보나치

반응형
import java.util.ArrayList;
import java.util.Arrays;

public class Fibonacci {
    public static void main(String[] args) {
        Fibonacci fb = new Fibonacci();
        int fib_naive = fb.fib_naive(10);
        int fib_recur_dp = fb.fib_recur_dp(10);
        int fib_dp = fb.fib_dp(10);
        System.out.println("fib_naive = " + fib_naive);
        System.out.println("fib_recur_dp = " + fib_recur_dp);
        System.out.println("fib_dp = " + fib_dp);
    }

    public int fib_naive(int n){
        if(n == 0) return 0;
        if(n == 1) return 1;
        int result = fib_naive(n-1) + fib_naive(n-2);
        return result;
    }

    ArrayList<Integer> fib_array = new ArrayList<>(Arrays.asList(0, 1));
    public int fib_recur_dp(int n ){
        if(n < fib_array.size()){
            return fib_array.get(n);
        }
        int fib = fib_recur_dp(n - 1) + fib_recur_dp(n - 2);
        fib_array.add(fib);
        return fib;
    }

    public int fib_dp(int n){
        if(n == 0) return 0;
        if(n == 1) return 1;

        ArrayList<Integer> fib_array = new ArrayList<>(Arrays.asList(0, 1));
        for(int i = 2; i < n+1; i ++){
            int num = fib_array.get(i - 2) + fib_array.get((i - 1));
            fib_array.add(num);
        }
        int result = fib_array.get(n);
        return result;
    }
}
반응형

'알고리즘 > Algorithm' 카테고리의 다른 글

Recursion의 응용 - 미로찾기  (0) 2021.01.19
2진검색 알고리즘  (0) 2021.01.19
Recursion(순환)-3  (0) 2021.01.19
Recursion(순환)-2  (0) 2020.07.05
선형 시간 알고리즘  (0) 2020.07.05