간단하게 요약해 동적계획법이란 복잡한 문제를 푸는 알고리즘의 한 종류로서, 큰 문제를 작은 문제로 나누고 작은 문제를 먼저 해결 한뒤에 결과를 바탕으로 큰 문제의 해답을 찾는 방법이다.피보나치 수열을 예로 들어보자. 피보나치 수열은 아래와 같이 표현할 수 있을 것이다. 하나의 수열 항목을 구하는 것에 대한 점화식을 알게 되면, 이를 반복하여 큰 문제에 대한 해답을 알아낼 수 있다. 동적 계획법 점화식 구현 방법 우리는 식을 세우는 것에 그치지 않고, 이것을 컴퓨터로 코딩해서 해를 구하는 프로그램을 만들어야 한다. 위 예로 든 피보나치 수열을 동적계획법으로 구현하기 위해서는 세가지 방식을 사용할 수 있을 것이다. 1. 다른 문제에서 가져오는 방식현재 노드의 값을 구하기 위해서 다른 곳(먼저 계산한 작은 문..