다이나믹 프로그래밍 기초

다이나믹 프로그래밍 DP는 주어진 문제를 여러개의 부분 문제들로 나누어 푼 다음, 그 결과들로 주어진 문제를 푸는 것이다.

이 개념은 분할 정복과 유사해보이지만 문제를 분할했을 때 겹치는 문제가 발생하지 않는 분할 정복에 비해, DP는 겹치는 문제가 발생한다. 이 겹치는 문제를 해결하기 위해 메모이제이션을 사용하는 것이다.

DP는 자신보다 작은 부분 문제의 답을 모두 알면 이번 문제를 빨리 풀 수 있다는 개념인데, 실제로 구현하려면 작은 문제의 답을 모두 알고있어야하기때문에 메모이제이션이 필요한 것이다.