[알고리즘] 다이나믹 프로그래밍 (DP)

다이나믹 프로그래밍은 최적화를 연구하는 수학 이론에서 온 것이다. 

큰 의미에서 분할 정복과 같은 접근방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고 이 답으로 부터 원래 문제에 대한 답을 계산해내기 때문이다. 그러나 차이점은 문제를 나누는 방식에서 생긴다. DP에서 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있기 때문에, 이 문제의 답을 여러번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀할 수 있다.

 

 

출처: 알고리즘 문제해결 전략(구종만)