題目解釋
你正在爬樓梯。需要 n
步才能到達頂部。
每次您可以爬 1
或 2
級台階。您可以透過多少種不同的方式登上頂峰?
範例
- 輸入:
n = 2
- 輸出:
2
There are two ways to climb to the top.
- 1 step + 1 step
- 2 steps
最佳解法
標準的 DP,細推後會發現 curr_step = res[i - 2] + res[i - 1]
的規律。
程式碼
class Solution:
def climbStairs(self, n: int) -> int:
res = [1, 2]
for i in range(2, n):
curr_step = res[i - 2] + res[i - 1]
res.append(curr_step)
return res[n - 1]
時間複雜度
O(n)
,n 是 n
的長度。
空間複雜度
O(n)
,res
的長度就是 n
。
結語
DP 基礎題。
Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤
(see all)
- [推薦工具] 讓程式碼截圖變的美美的吧!VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
- [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
- [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26