학습 일자 : 2023.

**DynamicProgramming (**동적 계획법)

어떠한 문제에 직면했을 때 부분적인 문제부터 해결하며 얻은 해답을 이용해 전체의 문제를 해결하는 상향식 접근 방식의 알고리즘.

분할 정복과는 반대의 개념임. 분할 정복이 top-down이라면, 동적 계획법은 botton-up 방법임.

동적 계획법 과정

1. 문제를 부분으로 나눔
2. 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장
3. 테이블에 저장되어 있는 부분 문제의 해답을 이용해 상위 부분 문제의 최적해를 구함.

[동적 계획법 예시]

| <피보나치 수열 > ❓피보나치 수열 : F(n+2) =F(n+1) + F(n)

1. 문제를 부분으로 나누면 N번의 수열을 구하기 위해 정수의 가장 작은 수인 0과 1의 합부터 시작해야 함
2. 가장 작은 수부터 점차적으로 큰 수의 합을 반환함
3. 가장 마지막 합이 바로 가장 상위 부분의 문제가 됨. | | --- | | <피보나치 수열 프로그램> 👩‍💻 [소스 확인하기] |

최장 공통 부분 순서

p.520