동적 프로그래밍

동적 프로그래밍(Dynamic programming)이란 어떠한 문제를 해결하기 위해서 그 문제의 부분 문제를 해결함으로서 효율적으로 문제를 해결하는 방법이다. 이는 1957년에 R. Bellman에 의해서 제안되었다.

동적 프로그래밍은 경제학, 제어이론등의 다양한 분야에 사용되고 있다.

최적 조건

임의의 동적 프로그래밍식이 최적화 문제에 대하여 최적임을 판정할 수 있는 조건은 벨만의 최적 원리이다. 또한, 이에 대한 필요 조건으로는 벨만 식이 있다.

예시

피보나치 수열

피보나치 수열(Fibonacci sequence)은 점화식 ${\textstyle F_{n}=F_{n-1}+F_{n-2}}$으로 정의되는 수열이다.

재귀적인 방법으로 계산을 시도하면, $O(\phi ^{N})$의 시간복잡도를 얻어서 매우 비효율적이라고 할 수 있다. 이를 개선시키기 위해서 동적 프로그래밍을 통해서 계산을 시도하면 $O(N)$의 시간복잡도를 얻고 효율적으로 계산할 수 있다.

하지만 더 효율적인 방법으로, 행렬 곱을 이용하여 $O(\log {N})$시간에 수행될 수 있다.

최대 공통 부분 문자열

최대 공통 부분 문자열(Longest common substring) 문제는 임의의 문자열 $S$, $T$가 주어졌을때, 최대의 길이의 공통된 부분 문자열을 찾는 문제이다.

두 문자열의 모든 부분 문자열을 돌아본다면, $O({|S|}^{2}{|T|}^{2})$의 시간복잡도를 얻지만, 동적 프로그래밍을 통해서 더 효율적으로 계산할 수 있다.

$DP[i][j]={\begin{cases}DP[i-1][j-1]+1,&{\text{if }}S_{i}=T_{j}\\0,&{\text{otherwise}}\end{cases}}$

다음과 같은 식은 $O(|S||T|)$시간에 계산될 수 있으며, 이는 효율적이다.