道しるべ-70.Climbing Stairs

質問する

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]