题目描述

假设你正在爬楼梯。需要 n 步你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：

输入： 2
输出： 2
解释：有两种方法可以爬到楼顶。

1 步 + 1 步

2 步

示例 2：

输入： 3
输出： 3
解释：有三种方法可以爬到楼顶。

1 步 + 1 步 + 1 步

1 步 + 2 步

2 步 + 1 步

我的解法

使用递归的思想，爬上第n阶台阶可以从第n-1阶和第n-2阶爬上，但是由于直接调用同名函数的时候超时，所以建一个列表，存储结果。
原答案：

class Solution:  
    def climbStairs(self, n):  
        result=[1,1]
        if n>=2:  
            for i in range(2,n+1):  
                result.append(result[i-1]+result[i-2])
        return result[n]

修改后答案：

class Solution:  
    def climbStairs(self, n):  
        result=[1,1]
        if n>=2:  
            for i in range(2,n+1):  
                result.append(result[i-1]+result[i-2])
        return result[n]

最优解法

类似的思路吧，只不过写法不同。

class Solution:
    global f
    f = collections.defaultdict(int)
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 0:
            return 0
        if n == 0:
            return 1
        if n in f.keys():
            return f[n]
        one_steps = self.climbStairs(n-1)
        two_steps = self.climbStairs(n-2)
        f[n] = one_steps + two_steps
        return f[n]