반응형
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 |