[白俊アルゴリズム]1727号:2×nタイル2

質問する
2×n矩形は1×2, 2×第1課×2つのタイルで充填された数を求めるプログラムを作成してください.
入力
最初の行はnです.(1 ≤ n ≤ 1,000)
しゅつりょく
1行目2×n矩形を充填する方法数を10007で割った後、残りを出力する.
コード#コード#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_11727 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] dp = new int[N + 2];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 3;

        for (int i = 3; i <= N; i++) {
            dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
        }
        System.out.println(dp[N]);
    }
}

答えと感じ
dpを利用して問題に近づいた.
2 x 1、1 x 2、2 x 2タイルが存在する.このとき,配列の末尾を埋めるようにdp点火式を確立した.
1 x 2を用いてdp[n−1]をどのように充填するかが重要である.
2 x 1を用いてdp[n−2]をどのように充填するかが重要である.
2 x 2を用いてdp[n−2]をどのように充填するかが重要である.
要するに、2 x 1充填を使用する場合と2 x 2充填を使用する場合は同じケースに相当する.そこで、点火式を作成する際に、dp[n−2]を2回行う.
最終的な点火式はdp[n]=dp[n−1]+dp[n−2]*2である.
参考資料