LeetCode Climbing Stairs

LeetCode解題之Climbing Stairs

原題

一共有n級樓梯，每次能夠爬一級或兩級，共有多少種不同的爬法爬到頂端。

注意點：

例子：

輸入: n = 6

輸出: 13

解題思路

典型的動態規劃題，遞推表達式為 dp[i]=dp[i-1]+dp[i-2]，n為1時只有一種方法，n為2時有兩種方法。

AC源碼

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 2:
            return n
        dp = [0 for __ in range(n)]
        dp[0] = 1
        dp[1] = 2
        for i in range(2, n):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n - 1]


if __name__ == "__main__":
    assert Solution().climbStairs(6) == 13