[leetcode-python3] 70. Climbing Stairs

1715 ワード
テキストリンク

70. Climbing Stairs - python3


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?
どうやってクリスマスツリーを描いたらいいかな
ルールがある気がするけど.(1,2,3,5,8,13...)
どう考えても私の頭では使えません^^同志たちに助けてもらいました

Other Answer 1:

class Solution:
    def climbStairs(self, n: int) -> int:
        if (n==1):
            return 1
        
        first = 1
        second = 2
        
        for i in range(3, n+1):
            third = first + second
            first = second
            second = third
        return second
フィボナッチ数列を利用
私が探しているルールはこれです.

(0)、1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987
直接計算してルールを探す場合、input=2は2なので、フィボナッチだと気づかなかったようですが…

Other Answer 2:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0 or n == 1 or n == 2:
            return n
        s1 = 1
        s2 = 2
        for i in range(2,n):
                s2 += s1
                s1 = s2 - s1
        return s2
実は理解の中で...
ピボナッチを見て、多分分かりました.
n=3からフィボナッチ数列で行います

Other Answer 3:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        dp = [0]*(n+1)
        dp[1] = 1
        dp[2] = 2

        for i in range(3,n+1):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n]
DPをよく使うらしい…私もこれが何なのか分かりません.
これもピボナッチを見て、たぶん分かった
dp=[0]*(n+1)=>n+1サイズの配列
残りはフィボナッチと同じです.
BOJ 9012括弧
Codeforces Round#250 D-The Child and Sequence/[TYVJ 3838]DQSとシーケンス(by帝江&Darkfalmes)