每日推薦一首歌：千裡之外——Jay Chou

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

每日至少一題：一題積分+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 階 + 1 階
2. 2 階

示例2：

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

1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 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]

速率明顯上來了。

其實還有好多種方法，大家可以試一試。

繼續看論文o(╥﹏╥)o

Reference

作者：力扣 (LeetCode)
鏈接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnumcr/
來源：力扣（LeetCode）

作者：數據結構和算法
鏈接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn854d/?discussion=DW6hWu
來源：力扣（LeetCode）

今日得分：+10+10
總得分：760

加油！！！