問題
原文
You are climbing a staircase. It takes
nsteps to reach the top.Each time you can either climb
1or2steps. 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：フィボナッチ数列(反復法)
|
1 2 3 4 5 6 7 8 9 |
#フィボナッチ数列(反復法) class Solution: def climbStairs(self, n: int) -> int: current_stair_path = 0 next_stair_path = 1 for i in range(n): current_stair_path = next_stair_path next_stair_path = current_stair_path + next_stair_path return next_stair_path |
解答2：フィボナッチ数列(再帰) →時間切れ
|
1 2 3 4 5 6 7 8 9 |
#フィボナッチ数列(再帰) → Time Limit Exceeded class Solution: def climbStairs(self, n: int) -> int: if n == 1: return 1 elif n == 2: return 2 else: return self.climbStairs(n-1) + self.climbStairs(n-2) |
解答3：フィボナッチ数列(メモ化再帰)
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#フィボナッチ数列(再帰・メモ化) class Solution: def climbStairs(self, n: int,table={}) -> int: if n == 1: return 1 elif n == 2: return 2 elif n in table: return table[n] else: table[n] = self.climbStairs(n-1,table) + self.climbStairs(n-2,table) return table[n] |
解答4：動的計画法？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution: def climbStairs(self, n: int) -> int: if n == 1: return 1 elif n == 2: return 2 else: dp = [1]*(n+1) dp[1] = 1 dp[2] = 2 for i in range(3,n+1): dp[i] = dp[i-2] + dp[i-1] return dp[-1] |
補足・参考・感想
参考
Pythonによるフィボナッチ数列の色々な求め方(一般項、反復法、再帰法) – Qiita
コメント