DP

한 번 풀었던 부분 문제에 대한 답을 저장해 놓았다가 해당 부분 문제를 다시 풀 일이 생기면 재사용하는 것이 메모리제이션이다.

DP 조건

1. 점화식 세우기
2. 종료 조건 찾기
3. 메모리제이션 처리 추가

1. 재귀 피보나치

1. 그냥 피보나치

import java.util.*;

public class DP_피보나치 {
	
	public static void main(String[] args) {
    
		System.out.println(fibo(10));
	}
	
	public static long fibo(int n) {
    
		if(n <= 1) return n;
		
		return mem[n] = fibo(n-1) + fibo(n-2);
	}

}

2. DP(메모리제이션)을 활용한 피보나치

✨이때 Stack에는 DFS처럼 분기별로 쌓인다고 생각하면 된다.

참고 문헌

🚨 하지만 일반 재귀 호출은 깊이가 10,000번 이하로 유지되어야 한다. 즉 아래 코드는 fibo(10,000)을 넣으면 Stack Overflow가 발생한다.

따라서 이때 취할 수 있는 방법은

• 반복문 : 재귀 호출 아얘 ❌
  -메모이제이션 : 재귀 호출 줄이기

import java.util.*;

public class DP_피보나치 {

	public static long mem[];
	
	public static void main(String[] args) {
		
		mem = new long[101];
		
		Arrays.fill(mem, -1);
		System.out.println(fibo(100000));
	}
	
	public static long fibo(int n) {
		
		if(mem[n] != -1) return mem[n];
		if(n <= 1) return n;
		
		return mem[n] = fibo(n-1) + fibo(n-2);
	}

}

3. DP + Stack Overflow 방지 코드

📌즉 이때는 작은 부분 문제부터 해결해 나가면 됩니다. 같은 부분 문제의 답은 항상 같다는 재귀 특성을 이용해서 작은 부분 문제부터 미리 풉니다.

for(int i = 0; i <= 100000; i++) {
	mem[i] = fibo(i);
}

import java.util.*;

public class DP_피보나치 {

	public static long mem[];
	
	public static void main(String[] args) {
		
		mem = new long[100001];
		
		Arrays.fill(mem, -1);
		
		for(int i = 0; i <= 100000; i++) {
			mem[i] = fibo(i);
		}
		System.out.println(fibo(100000));
	}
	
	public static long fibo(int n) {
		
		if(mem[n] != -1) return mem[n];
		if(n <= 1) return n;
		
		return mem[n] = fibo(n-1) + fibo(n-2);
	}

}

2. 순차 누적 피보나치

fibo(n) = fibo(n-1) + fibo(n-2)
즉 바꿔 말하면 f(n)은 f(n+1)과 f(n+2)에 영향을 미친다는 뜻. 다라서 순차 누적으로 DP를 구현할 수 있다.

long[] mem = new long[n+1]
mem[0] = 0;
mem[1] = 1;

for(int i = 0; i <= n - 1; i++){
	mem[i+1] += mem[i];
    if(i+2 < mem.length){
    	mem[i+2] += mem[i];
    }
} 
return mem[n];