道しるべ-70.Climbing Stairs

715 ワード
道しるべ テキストリンク

質問する


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?

に答える


与えられた条件下でn次のすべての方法の問題を計算した.典型的なDPアルゴリズム応用問題については,インデックス0,1,2に加えて,dp[n]=dp[n−1]+dp[n−2]式を適用することで容易に解決できる.
  • インデックス0,1,2を除いては,1次2次的に上げることができるので,上記式では+1の方法が増加する.
  • DPは、アップとダウンの2つのケースがあり、対応する問題は、ダウンによって解決される速度がより速い.
  • ですが、上へ行くのがもっと簡単なので、上へ展開するのを使います.

    • コード#コード#

    class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0, 1, 2]
        for i in range(3,n+1):
            dp.append(dp[i-1] + dp[i-2])
        return dp[n]
    [アルゴリズム]反転された小数点-ブレークポイント力(完全ナビゲーション)
    [アルゴリズム]石ハサミ布