題目解釋
你正在爬樓梯。需要 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 基礎題。
𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art
Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 
(see all)
(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
