41.LeetCode70.爬楼梯

• 标签： 动态规划
• 难度： 简单

---

• 题目描述

• 解法1（递归）： 超时

经观察分析，当 阶数 = n 时， 方法数等于f(n-1)和 f(n-2), 不难写出如下递归代码。

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if(n==0):
            return 0
        elif(n==1):
            return 1
        else return climbStairs(n-1) + climbStairs(n-2)

• 解法2

由 f(n) = f(n-1) + f(n-2)可知：从f(1) = 1，f(2) = 2开始， 可以依次递推出 f(3),f(4),.....直到 f(n) 的值 。模仿这个从小到大，依次递推的过程，不难实现如下代码：

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if(n==1):
            return 1
        elif(n==2):
            return 2
        else:
            dp = []
            dp.extend([1,2])
            while(len(dp)<n):
                dp.append(dp[-1] + dp[-2])
            return dp[-1]

• 其他解法

暂略。