2xn 타일링 문제입니다.
   
주어진 타일은 1x1 2x1 2x2 타일 총 세가지가 있습니다.

1x1 2x1 로 n-1 번째 까지 채우는 2가지 경우가 있고

2*2 로     n-2 번째 까지 채우는 1가지 경우가 있습니다.

d[n] =     (n-1) + 2 * (n-2)

라는 점화식이 도출 가능합니다.

package problem.dynamic.Q11727;
import java.io.*;

public class Main_11727 {
    static int d[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        d = new int[n+1];
        bw.write(Integer.toString(tiling(n)));

        bw.flush();
        bw.close();
        br.close();
    }
    public static int tiling(int n){
        if(d[n]>0)
            return d[n];
        if(n<=1){
            d[n] = 1;
        }
        else {
            d[n] = (tiling(n - 1) + tiling(n - 2)*2) % 10007 ;
        }
        return d[n];
    }
}