問(wèn)題描述

你正在爬樓梯。需要 n 步你才能到達(dá)頂部。

每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方式可以爬到樓頂呢？

注意：給定 n 將是一個(gè)正整數(shù)。

解答方法

這實(shí)質(zhì)上是一個(gè)Fibonacci數(shù)列。

先直接使用函數(shù)遞歸，發(fā)現(xiàn)如何修改函數(shù)遞歸都超時(shí)。

后面改為用list將前面的數(shù)存下來(lái)，用的時(shí)候直接取出的方式，運(yùn)行通過(guò)。

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]