Dynamic programming은 어떤 상태에서의(n) 최적화된 솔류션 S(n)은 그 전의 최적화된 상태에 의해서 조합될수 있는 경우 적용이 가능하다.
예를 들어 "동전에 숫자가 1,3,5 로 적혀 있을 경우 합이 11인 최소의 동전 개수는?"에 대한 최적의 솔류션은
1. 합이 10인 솔류션 + 숫자1이 쓰여진 동전 1개
2. 합이 8인 솔류션 + 숫자3이 쓰여진 동전 1개
3. 합이 5인 솔류션 + 숫자5가 쓰여진 동전 1개
이 3가지 솔류션중 가장 동전 수가 작은 것의 동전 수가 답이다.
즉 S(11)=MAX(S(10),S(8),S(5))+1 이 된다.
일반적으로 S(n)=MAX(S(n-1),S(n-3),S(n-5))+1 이며 이를 기반하여 위의 예제를 풀어 보면
0. S(0)=0
1. S(1)=MAX(S(0))+1=1
2. S(2)=MAX(S(1))+1=2
3. S(3)=MAX(S(2),S(0))+1=1
4. S(4)=MAX(S(3),S(1))+1=2
5. S(5)=MAX(S(4),S(2),S(0))+1=1
....뭐..이런 식이다.
다른 예를 들어 보면
LCS(Longest Common String)인데 DNA분석에 있어서 가장 긴 공통 문자열을 의미하는데,
예를 들어 GATTACGTC와 GTACAAT에서 LCS는
G A T T A C G T C
G T A C A A T
G T A C T 가 될것이다(맞나??) 이것도 잘 보면
X(m) 및 Y(n)의 문자열에 대해서
만약 X(m)==Y(n)이면 LCS(m,n)=LCS(m-1,n-1)+1이 된다.
X(m)!=Y(n)이면 LCS(m,n)= MAX(LCS(m-1,n),LCS(m,n-1))이 된다.
