＜LeetCode天梯＞Day037 爬樓梯（遞歸+動态規劃） | 初級算法 | Python

以下為我的天梯積分規則：

每日至少一題：一題積分+10分

若多做了一題（或多一種方法解答），則當日積分+20分（+10+10）

若做了三道以上，則從第三題開始算+20分（如：做了三道題則積分-10+10+20=40；做了四道題則積分–10+10+20+20=60）

初始分為100分

若差一天沒做題，則扣積分-10分（周六、周日除外注：休息）

堅持！！！

初級算法

刷題目錄

動态規劃

題幹

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數。

示例1：

輸入： 2

輸出： 2

解釋： 有兩種方法可以爬到樓頂。

1 階 + 1 階

2 階

示例2：

輸入： 3

輸出： 3

解釋： 有三種方法可以爬到樓頂。

1 階 + 1 階 + 1 階

1 階 + 2 階

2 階 + 1 階

遞歸

分析：

有大佬說這道題和青蛙跳台的原理一樣。

當n=1時，隻一次即可，f(1)=1;

當n=2時，可以有兩次，f(2)=2;

當n=3時，有三次，f(3)=f(2)+f(1);

借用下圖檔：

class Solution:
    def climbStairs(self, n: int) -> int:
        # 遞歸
        if n <= 1:
            return 1
        if n < 3:
            return n
        return Solution.climbStairs(self, n-1) + Solution.climbStairs(self, n-2)      

直接逾時，這樣遞歸，有點慢啊！

這兒還是不用遞歸了，改用非遞歸吧。

非遞歸

其實也是用的那個Fibonacci的方法。

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