白準アルゴリズム10826号:フィボナッチ数4

リンク

https://www.acmicpc.net/problem/10826

質問する

フィボナッチ数は0と1で始まる.0番目のフィボナッチ数は0で、1番目のフィボナッチ数は1です.2番目から前の2つのフィボナッチ数の和です.
このようにしてFn=Fn−1+Fn−2(n≧2)となる.
n=17までは、次のようにフィボナッチ数を用いる.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
nが与えられると,n次フィボナッチ数を求めるプログラムを記述する.

入力

最初の行はnです.nは10000以下の自然数または0である.

しゅつりょく

1行目はn番目のフィボナッチ数を出力する.

入力と出力の例

プールコード(Python)

n = int(input())

dp = [0 for i in range(10001)]

dp[0] = 0
dp[1] = 1
dp[2] = 1

for i in range(3,n+1,1):
  dp[i] += dp[i - 1] + dp[i - 2]

print(dp[n])