AtCoder ABC 006 B – トリボナッチ数列 Python解説

スポンサーリンク

トリボナッチ数列

今回の問題はこちらから「トリボナッチ数列」。トリボナッチ数列とは、フィボナッチ数列の言わば兄弟のようなもので、この数列は3つ前までの数字を足したものになります。

3つ前までの数字を使うので、あらかじめ最初に使う3つの数字は手作業で準備します。問題ではa1=0、a2=0、a3=1までを準備したら、あとはfor文で処理しましょう。

n = int(input())

dp = [0, 0, 1]

for i in range(3, n + 1):
    dp.append(dp[i - 1] + dp[i - 2] + dp[i - 3] % 10007)
    
print(dp[n - 1])

最後に余りを求めると、数値がオーバーフローする場合があるので、随時10007で余りを求めています。

n = int(input())
dp = [0] * (n + 3) #3以下だとdp[0]、dp[1]、dp[2]までが範囲外のエラーになるためn + 3している
dp[0] = 0
dp[1] = 0
dp[2] = 1
for i in range(3, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 10007
print(dp[n - 1])

上記のコードとは、appendを使うか使わないかぐらいの違い。
こちらのコードでは、先に使うであろう数の配列を用意して0で初期化し、あとから数字を更新していっている。