白駿1904 01タイル

https://www.acmicpc.net/problem/1904
ルールが見つかりました.N=1->1,N=2->2.
n=3の場合、端数を1と00の場合に加算すればよい.では,最終的にN=2とN=1の場合,ケースの数を加算すればよい.結局フィボナッチ.
しかし,再帰関数の形で解くと,テストボックスは正しいが,常に深さを超える.

import sys

def tile(N):
    if N == 1:
        return dp[1]
    elif N == 2:
        return dp[2]

    dp[N] = tile(N-1) + tile(N-2)
    return dp[N]

N = int(sys.stdin.readline().strip())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2
print(tile(N) % 15746)

検索すると再帰関数のパフォーマンスが悪いことがわかりました.
だから私は一つ一つ計算すればいいです.

import sys
N = int(sys.stdin.readline().strip())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

for i in range(3, N+1):
    dp[i] = (dp[i-1] + dp[i-2])%15746
print(dp[N])