87. Climbing Stairs

4844 ワード
アルゴリズム#アルゴリズム# テキストリンク
道しるべ
  • 階段を登っています.ピークに達するためにはn級に登る必要があります.
    毎回1級または2級に登ることができれば、ピークに達する方法を計算するにはどのような方法がありますか.


    • 1.再帰構造ツリーの原形（タイムアウト）

    

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

  • 考えてみれば、解くのは容易ではない.すべての場合の数を見つけるのは、かなり難しいように見えます.

  • 下図に示すように、一例を描くごとに、基本的にはフィボナッチ数と同じタイプの問題があります.
  • しかなく、方法や形式が異なり、連想しにくく、同じ方法で解くしかない.
  • の新しいタイプの問題をフィボナッチ数列などの既存の有名な問題と結びつけて解く方法は問題を解決する良い方法
    • である.
  • この方法はタイムアウトで解決できない.ダイナミックプログラミングしか利用できません.

    • 2.注記再構築（40ミリ秒）

    

class Solution:
    dp = collections.defaultdict(int)
    
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        
        if self.dp[n]:
            return self.dp[n]
        self.dp[n] = self.climbStairs(n - 1) + self.climbStairs(n - 2)
        return self.dp[n]

  • この解のすべてのコードを見ると,フィボナッチ数の初期値とはわずかに異なり,注釈では同じである.
  • は実際には同じコードであり、もちろん実行も速い.
    • [アルゴリズム]重複していないアルファベット語の長さを返す
    BYTEとCBitmap間の変換