【LeetCode】 70. Climbing Stairs 解答・解説【Python】

この記事は約3分で読めます。

 

問題

原文

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Example 2:

 

Constraints:

  • 1 <= n <= 45

内容

あなたは階段を上っています。最上段まではn段あります。各段では1段か2段上がることができます。最上段まで上るのに何通りの方法があるでしょうか?

 

例1:n=2(階段が2段)の時、2通りの登り方があります。

1. 1段ずつ上がる

2. 2段をまとめて上がる

例2:n=3の時、3通りの登り方があります。

1. 1段+1段+1段

2. 1段+2段

3. 2段+1段

 

制約

1<= n <= 45

 

※正しくない可能性があります。

方針

今の段数までの登り方は、1段下までと2段下までの登り方の合計値になります。

xを階段の登り方の通り数だとすると↓のようになるのではないかと思います。(数学苦手なので間違っていたらごめんなさい)

x = (x-1) + (x-2)

これを以下のようにコードにかけるかと思いました。

➀フィボナッチ数列

②動的計画法(あっているかわかりません)

・最上段までの登り方を漸化式で考えます。

・1,2段目のみ初期値で入力し、残りは漸化式をコードに書いて求めます。

解答

解答1:フィボナッチ数列(反復法)

解答2:フィボナッチ数列(再帰) →時間切れ

 

解答3:フィボナッチ数列(メモ化再帰)

 

解答4:動的計画法?

 

補足・参考・感想

参考

Pythonによるフィボナッチ数列の色々な求め方(一般項、反復法、再帰法) – Qiita

 

 

前:67. Add Binary

次:100. Same Tree

LeetCode 解答・解説記事一覧

コメント