[BOJ] 2306번: 유전자

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

D[i][j]를 DNA[i~j] 내의 가장 긴 유전자 길이라고 정의할 때, D[i][j]는 k = i~j에 대해 D[i][k] + D[k+1][j]의 최댓값입니다.(그리고 만약 DNA[i] = a, DNA[j] = t이거나 DNA[i] = g, DNA[j] = c일 경우, D[i+1][j-1]+2도 고려해주어야 합니다.)

이 점화식이 성립하는 이유는, 만약 DNA[i~j] 내의 최대길이 DNA가 여러 조각으로 잘릴 수 있다면 어떤 k =i~j에 의해 D[i][k]+D[k+1][j]의 합으로 D[i][j]를 나타낼 수 있고, 여러 조각으로 잘리지 않는 형태라면 반드시  DNA[i] = a, DNA[j] = t이거나 DNA[i] = g, DNA[j] = c 이기 때문입니다.

테이블을 채우는 방향은 j-i가 커지는 순서로 채우면 됩니다.

https://github.com/encrypted-def/BOJ/blob/master/2306.cpp