【Leetcode 筆記】70. Climbing Stairs

題目解釋

你正在爬樓梯。需要 n 步才能到達頂部。
每次您可以爬 1 或 2 級台階。您可以透過多少種不同的方式登上頂峰？

範例

• 輸入: n = 2
• 輸出: 2

There are two ways to climb to the top.

1. 1 step + 1 step
2. 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 基礎題。

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

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