[アルゴリズム]プログラマ-2 x nタイル

プログラマ-2 x nタイル

説明する

def solution(n):
    MAX_LENGTH = 60001
    MOD = 1000000007

    dp = [0] * MAX_LENGTH
    dp[1] = 1
    dp[2] = 2
    for i in range(3, MAX_LENGTH):
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
    return dp[n]

i第2のタイルを作製する方法は、i−1の作製方法において、縦に1つのタイルを貼り付けるか、i−2の作製方法において横に2つのタイルを貼り付けることである.