DP

• 동적 프로그래밍(동적 계획법)

• 다이나믹 프로그래밍 : 큰 문제를 작은 문제로 나눠서 푸는 알고리즘, 최적화

• 조건 : Overlappint Subproblem 부분 문제들이 중복됨 (피보나치 수 n = (n-1) + (n-2))
  Optimal Substructure(큰 문제의 정답을 작은 문제의 정답에서 구할 수 있음) 부분 문제의 최적 해가 문제의 최적해가 됨

• 다이나믹프로그래밍에서 각각의 작은 문제는 한 번만 풀기

• Optimal Substructure를 만족하기 때문에, 같은 문제는 여러번 풀어도 답이 같음

• 그러므로 답을 한 번 구하면 저장해 놓기 -> Memoization

• 피보나치 수

int fibo(int n) {
	if(n <= 1){
    	return n;
    }
    else {
    	return fibo(n-1) + fibo(n-2);
   }
}

: 계속해서 재귀를 수행해서 별로인듯하다

중복되는 호출 발생 - 처음 답을 구한 후 이를 저장한 후 종복 호출이면 메모해 놓은 값을 사용(메모이제이션)

int memo[100];
int fibo(int n) {
	if(n <= 1){
    	return n;
    }
    else {
   		if(memo[n] > 0){ // 저장되어 있는지 체크한 후
        	return memo[n];
        }
    	memo[n] = fibo(n-1) + fibo(n-2);
        return memo[n];
   }
}

• 다이나믹 프로그래밍 풀이 방법

• Top-down : 재귀 이용
• Bottom-up : 반복문 이용

int memo[100];
int fibo(int n){
	memo[0] = 0;
    memo[1] = 1;
    for(int i = 2; i <= n; i++){
    	memo[i] = memo[i-1] + memo[i-2];
    }
    return memo[n];
} // Bottom-up