[Leetcode][python]Climbing Stairs/爬楼梯

题目大意

一共有n级楼梯，每次能够爬一级或两级，共有多少种不同的爬法爬到顶端。注意：第一级楼梯也要上，也就是说第二个楼梯就有两种走法。

解题思路

动态规划，状态转移方程式：

dp[i] = dp[i-1]+dp[i-2]

代码

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

总结