다이나믹 프로그래밍(Dynamic Programming)

다이나믹 프로그래밍(dp)이란

- 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 기법.

- 작은 문제들의 해결책을 저장해두고 재사용.

 

 

다이나믹 프로그래밍이 적용되기 위한 조건

- 최적 부분 구조: 큰 문제의 최적해가 작은 문제의 최적해로 이루어짐

- 중복되는 부분 문제: 동일한 작은 문제들이 반복해서 나타남

 

 

구현 방식

Top-down(하향식): 메모이제이션

Bottom-up(상향식): 타뷸레이션

 

 

대표적인 dp유형

- 피보나치

- 계단 오르기

- 동전 교환

 

 

 

내가 문 문제

백준2775

백준1463