동적 프로그래밍에 대해 설명해 주세요.

• 동적 프로그래밍이란 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 해결하는 방식이다.

• 동적 프로그래밍의 가장 큰 장점은 어떤 부분 문제가 다른 문제들을 해결하는 데 사용될 수 있어, 답을 여러 번 계산하는 대신 한 번만 계산하고 그 결과를 재활용하는 메모이제이션 기법으로 속도를 향상 시킬 수 있다는 점이다.

꼬리 질문

동적 프로그래밍으로 문제를 해결하기 위한 두 가지 조건

1. 중복되는 부분 문제 : 주어진 문제는 같은 부분 문제가 여러 번 재사용된다.

2. 최적 부분 구조 : 새로운 부분 문제의 정답을 다른 부분 문제의 정답으로부터 구할 수 있다.