Tile Code (UVa Live Archive Asia - Site 4 (Korea) - 2007/2008 Seoul (Korea))

UVa Live Archive Online Judge

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3904

問題

2*nの領域に1*2、2*1、2*2のタイルを敷き詰めたい。タイルの敷き詰め方は何通りあるか？ただし、左右でひっくり返して同じになる場合は同じ置き方とみなす。
3<=n<=30

解法

DPですべての場合と左右対称な場合を数えて足して2で割る。