ALDS1 10A フィボナッチ数列

この記事で使うアルゴリズム

動的計画法

全問題の一覧はこちらです

この問題は動的計画法を用いて解くことができます。

動的計画法と言っても構える必要はありません。漸化式もシンプルでとても基本的な動的計画法と言えるでしょう。

クエリに関係なく最大サイズのフィボナッチ数列を用意しておき、クエリに応じて数列を参照する実装としました。

N = 45
dp = [0] * N
dp[0] = dp[1] = 1
for i in range(N-2):
    dp[i+2] = dp[i] + dp[i+1]
n = int(input())
print (dp[n])