问题描述

你正在爬楼梯。需要 n 步你才能到达顶部。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方式可以爬到楼顶呢？

注意：给定 n 将是一个正整数。

解答方法

这实质上是一个Fibonacci数列。

先直接使用函数递归，发现如何修改函数递归都超时。

后面改为用list将前面的数存下来，用的时候直接取出的方式，运行通过。

class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<3:
            return n
        else:
            i=3       
            l=list(range(n+1))         
            while i<=n:
                l[i]=l[i-1]+l[i-2]
                i=i+1
            return l[n]