【yukicoder】No.44 DPなすごろく

お馴染み yukicoder で勉強です。慣れてきたので簡単な問題はサクサクコードかけるようになってきました。

問題

問題はこちら

解法

動的計画法(DP: Dynamic Programming)です。中でも一番よく聞く簡単なフィボナッチ数列です。

]

数式にすると次の関係があります。

今回の問題では マス目に行くパターンの数を求めます。パターンの数を とすると、

マス目に行くパターンは マス目で１進む場合と、 マス目で２進む場合なので、 となります。

Python3

コード

n=int(input())
a=0
b=1
for i in range(n):
    t=a+b
    a=b
    b=t
print(b)