다이나믹 프로그래밍의 정의

: 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아 올려 주어진 문제를 해결하는 알고리즘

• 피보나치 수열

/* 재귀 시간복잡도 : O(log n)*/
int fibo(int n){
	if(n <= 1) return 1;
	return fibo(n-1) + fibo(n-2)
}
/* DP  시간복잡도 : O(n)*/
int fibo(int n){
	int f[20];
	f[0] = f[1] = 1;
	for(int i = 2; i <= n; i++)
		f[i] = f[i-1] + f[i-2];
	return f[n]
} 

• fibonacci 테이블

DP 푸는 과정

1. 테이블 정의하기
2. 점화식 찾기
3. 초기 값 정하기

<aside> 🔥 연습 문제

<aside> 🔥 1. BOJ 1463 : 1로 만들기

• 테이블 정의

  • D[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값

• 점화식 찾기

  • D[12] = ?
  • 3으로 나누거나 (D[12] = D[4] + 1)
  • 2로 나누거나 (D[12] = D[6] + 1)
  • 1을 빼거나 (D[12] = D[11] + 1)

  → D[12] = min(D[4] + 1, D[6] + 1, D[11] + 1)

  → D[k] = ?

  → 3으로 나누거나(D[k] = D[k/3] + 1)

  → 2로 나누거나 (D[k] = D[k/2] + 1)

  → 1을 빼거나 (D[k] = D[k-1] + 1), 이들 중에서 최소값

• 초기값 정의하기

  • D[1] = 0 </aside>

<aside> 🔥 2. BOJ 9095 1, 2, 3 더하기

1. 테이블 정의

   1. D[i] = i를 1, 2, 3의 합으로 나타내는 방법의 수

2. 점화식 찾기

   1. D[4] = ?

   1 + 1+ 1 + 1, 3 + 1, 2 + 1+ 1, 1+ 2 + 1

   (3을 1, 2, 3의 합으로 나타내는 방법) + 1, D[3]

   1 + 1 + 2, 2+ 2

   (2를 1, 2, 3의 합으로 나타내는 방법) + 2, D[2]

   1 + 3 (1을 1, 2, 3의 합으로 나타내는 방법) + 3, D[1]

   → D[4] = D[1] + D[2] + D[3]

</aside>

</aside>