動的計画法を用いて階段の登り方の通り数求める Davis' Staircase in Hacker Rank

問題

始め階段の0段目にいて、N段目までの登り方の方法の数を求める問題。 階段は1段、2段又は3段を一気に登る事ができる。

www.hackerrank.com

解法

全列挙するためには、今いる段から1段登るか2段登るか3段登るかの3通りを毎回行うので、3N通り行わ無ければならない。 動的計画法を用いることでO(N)で求める事ができる。

ソースコード