왼칸부터 채워나가면 나올 수 있는 다음 판의 상태가 2가지밖에 없어요.

그 2가지 판을 채우는 경우를 재귀로 구하시면 될 거 같아요.

AA#
BB#
CC#

AA#
B##
B##

A##
A##
BB#

첫번째는 다시 꽉찬 3N 이 나오는데 두번째, 세번째는 2줄+3줄~ 이네요. 이렇게 2가지 상태밖에 없고 겹치는 경우는.. 없을 거 같은데요?

###
###
X##

를 채우는건

AA#
BB#
XCC

A##
A##
X##

이렇게 2개밖에 없겠네요.

@joonas 예상 외의 답변이라.. 잘 이해가 안됩니다. 제가 말한 dp[i][1]에 대해서 설명해주신건가요? A,B,C,#이 무얼 뜻하는지도 궁금합니다. 

dp[i][0] 에서 i가 i번째 줄까지의 상태 아닌가요? 저도 "짝수일때 타일의 독립적인 부분", "겹치는 부분" 이라는게 뭘 말씀하시는 지 잘 이해를 못했어요.

#는 빈칸을, AA BB 는 같은 알파벳끼리 하나의 덩어리를, X는 이미 채워진 칸을 표현했습니다. 타일이 그 모양으로 있는거지요. 
처음 3개의 모양이 3xN 에서 나올 수 있는 (왼쪽칸부터 채우는) 경우이고, 나머지는 그렇게 채운 과정에서 첫칸이 2줄+이후에 3줄을 (왼쪽칸부터) 채우는 경우입니다.

아무래도 이 링크가 더 설명을 잘 했을 것 같네요. 도움이 되시면 좋겠습니다.

@joonas 감사합니다 참고하고 다시 풀어보겟습니다