BOJ 12950 - 팰린드롬 보행

BOJ 12950 - 팰린드롬 보행

$dp[l][i][j]=$현재 $l$길이의 팰린드롬이고 $i$노드와 $j$노드에 있다고 하자.

현재 $i=j$ 라면 짝수 길이의 팰린드롬을 찾은 것이다.

$i$의 간선 중 $j$로 가는 것이 있다면 홀수 길이의 팰린드롬을 찾은 것이다.

점화식은 $i$의 간선과 $j$의 간선 쌍 중 같은 알파벳을 가지는 것의 상태를 변경 시켜준다.

따라서 $O(LM^2)$ 정도면 찾을 수 있다.

$L$은 $l$을 어디까지 진행시켜야 할지인데, 최악의 경우 한 쪽에서 간선이 하나 남았는데 그 간선은 무조건 홀수 길이의 팰린드롬에서 가장 중앙에 위치하는 경우이다.

대충 이러한 경우는 $N=20$ 이기때문에 매우 작기 때문에 $L=100$ 정도로 두고 돌려줘도 돌아간다.