9251

이 알고리즘을 이해하기 위해서는 확 와닿는 예제가 필요하다.. KCSESE 와 CCCCKC 가 있다고 치자. 답은 눈에 보이다시피 KC의 길이인 2이다. 부분수열을 전부다 구하면 시간내에 못들어온다. 그래서 이걸 동적계획법으로 구해야한다. 점화식을 세워야한다. 우선 A 문자열이 빈 상태로 시작하고, 동적으로 구할 것이므로, 하나씩 원소를 추가한다. A 문자열에 문자가 하나 추가되면 B문자열은 이 추가된 항목에 대해 점화식을 적용한다. 첫 원소가 추가되었다. A 문자열은 이제 A이다. 출발해본다. 이제 차례대로 C, CC, CCC, CCCC, CCCCK, CCCCKCK 와 비교할 것이다. K C A의 마지막 원소 A와 추가된 원소 C를 비교한다. 누가 봐도 다르다. 일단 넘어간다. K CC 이번에 B에 추..