階段を上る(Top-Down:コメント作成)

ダイナミックプランニング

に質問

階段を上る(Top-Down:コメント作成)

哲洙は階段を上がる時、一度に1段か2段を上がる.全部で4段上がると,その方法は1+1+1,1+1+2,1+2+1,2+1,2+2の5種類である.
では、全部でN段の階段がある場合、撤退して上がれる方法は何種類ありますか?

■説明の入力
1行目は自然数N(3≦N≦45)であり,これはステップ数である.
■出力説明
最初の行のメソッド数を出力します.
■入力例1
7
■出力例
21

コード#コード#💻

import sys
#sys.stdin = open("input.txt", "rt")			# read text

def DFS(len):
    if dy[len] > 1:
        return dy[len]
    if len == 1 or len == 2:
        return len
    else:
        dy[len] = DFS(len-1) + DFS(len-2)
        return dy[len]

if __name__ == "__main__":
    n = int(input())
    dy = [n] * (n + 1)
    print(DFS(n))

リファレンス

インフラストラクチャ:Pythonアルゴリズム回答