題目描述

假設(shè)你正在爬樓梯。需要 n 步你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個(gè)正整數(shù)。
示例 1：

輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。

1. 1 步 + 1 步
2. 2 步

示例 2：

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。

1. 1 步 + 1 步 + 1 步
2. 1 步 + 2 步
3. 2 步 + 1 步

我的解法

使用遞歸的思想，爬上第n階臺(tái)階可以從第n-1階和第n-2階爬上，但是由于直接調(diào)用同名函數(shù)的時(shí)候超時(shí)，所以建一個(gè)列表，存儲(chǔ)結(jié)果。
原答案：

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]

最優(yōu)解法

類似的思路吧，只不過(guò)寫法不同。

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]