Search

DP(다이나믹 프로그래밍)

•
주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 방법이다. 하위의 문제들이 반복되어 계산되는 것을 보완하여 고안되었는데, 문제를 관통하는 점화식을 구해 그를 통해 문제를 해결한다. 하위 부터 계산하여 상위로 올라가는 BOTTOM-UP 방식과 상위부터 시작하여 하위로 내려가는 TOP-DOWN 방식이 있다.