동적 계획법(Dynamic programming)

동적 계획법이란 주어진 문제를 여러 개의 부분으로 나누어 푼 다음 그 결과들을 조합하여 주어진 문제를 푸는 방법이다

큰 문제를 작은 문제로 나눈다는 측면에서 분할정복 알고리즘과 비슷하지만 두 알고리즘간의 차이점은 분할 정복은 문제를 분할했을 때 겹치는 부분 문제가 발생하지 않지만 동적 계획법은 겹치는 문제가 발생하기 때문에 부분 문제 결과값을 메모이제이션을 해서 최적화를 해줘야 한다

그리고 분할정복은 나눈 문제들을 완전히 새로운 하나의 독립된 새로운 문제로 보지만 동적 계획법은 이전에 계산한 부분 문제의 결과값에 의존적이다

마지막으로 분할정복 알고리즘은 문제를 나눴을 때 성능이 향상되는 상황에서 사용하지만 동적 계획법은 나눴을 때 겹치는 부분 문제의 결과를 재사용하여 성능이 향상되는 상황에서 사용한다

다이나믹 프로그래밍 알고리즘을 적용하기 위한 조건

중복되는 부분 문제 (Overlapping Subproblem)

부분 문제의 결과값을 다른 부분 문제의 결과값을 구할 때도 이미 계산한 부분 문제의 결과값을 여러번 사용하는 경우 ex) 피보나치 수열 알고리즘

최적 부분 구조(Optimal Substructure)

문제의 최적해가 부분 문제의 최적해를 포함하고 있는 경우 ex) 막대 자르기 알고리즘, 배낭 알고리즘 등