유전자

https://www.acmicpc.net/problem/2306

풀이

• 풀어본 DP 문제 중 제일 어려움

• d[i, j]

    a[i..j] 의 부분 KOI 유전자 들 중 가장 긴 것의 길이
  

  ​

1. d[i, j] = 2

   • a[i..j] == “at”
   • a[i..j] == “gc”

2. d[i, j] = d[i+1, j-1] + 2

   • a[i]==”a” , a[j]=”t”
   • a[i]==”g” , a[j]=”c”

3. d[i, j] = d[i, k] + d[k+1, j]

- a[i...k] 의 부분 KOI 유전자 들 중 가장 긴 것의 길이 => d[i, k]

- a[k+1...j] 의 부분 KOI 유전자 들 중 가장 긴 것의 길이 => d[i, k]