DP - 피보나치 수열 구하기

DP

• 하나의 문제는 단 한번만 풀도록 하는 알고리즘
• 계산한 결과는 테이블(배열)에 저장 _메모이제이션 기법

1. 점화식 세우기
   ex) 피보나치 : n = n-1 + n-2
2. 테이블(배열)만들기
   ex) static int[ ] d;
3. 초기값 정하기
   d[0] = 0;
   d[1] = 1;
4. 배열 채워넣기(Bottom-up 방식)
   for(int i = 2; i <= n; i++){
   d[i] = d[i-1] + d[i-2];
   }

import java.io.*;
public class Main{
	//테이블 만들기 (메모이제이션)
	static int[] d;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        d = new int[n+1];
        //초기값 정하기
        d[0] = 0;
        d[1] = 1;
        //배열 채워넣기
        for(int i = 2; i <= n; i++){
        	d[i] = d[i-1] + d[i-2];
        }
		System.out.println(d[n]);
	}
}        

* Top-down 방식

import java.io.*;
public class Main{
	//테이블 만들기 (메모이제이션)
	static int[] d;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        d = new int[n+1];
        //배열 초기화 하기(값이 입력되기 전 상태로 초기화)
        for(int i = 0; i <= n; i++){
        	d[i] = -1;
		}
        //초기값 정하기
        d[0] = 0;
        d[1] = 1;
        //배열 채워넣기
        fibo(n);
		System.out.println(d[n]);
	}
    static void fibo(int n){
    	if(d[n]  != -1){	//계산한적이 있으면 배열에서 찾아서 return
    		return d[n];
        }
  		d[n] = fibo(n-2) + fibo(n-1)
  		return d[n];
    }
}        

• Bottom-up VS Top-down
  큰 상관은 없지만 바텀-업이 안전&퍼포먼스 좋음, 탑-다운이 구현하기 쉽다고 함
  내가 볼 땐 바텀업이 더 직관적이고 쉬워보임
• 주어진 문제의 범위가 크지 않으면 dp문제일 가능성
• 점화식 찾는 팁 : 테이블 직접 손으로 채워보기