동적 계획법(Dynamic Programming)
주어진 문제 전체를 일련의 부분 문제로 분해하여 각 부분을 메모이제이션 하면서 작은 문제에서 큰 문제로 순서대로 답을 구하는 방법
- 핵심 : 무수히 많은 상태를 얼마나 잘 정리하여 부분 문제로 구성
동적 계획법은 분야를 넘나들며 다양하게 적용할 수 있다.
- 냅색 문제
- 스케줄링 문제
- 발전 계획 문제
- 편집 거리(diff 명령어)
- 음성 인식 패턴 매칭 문제
- 문장 띄어쓰기
- 은닉 마르코프 모델
문제의 폭이 넓은 대신에 적용하는 패턴이 다앙하여 습득하기 어려운 단점이 있다.