39%
Loading ...

【Leetcode 筆記】70. Climbing Stairs

題目解釋

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

範例

  • 輸入: 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 基礎題。

數據女巫 𝔻.𝕡𝕪𝕤 🔮

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

The reCAPTCHA verification period has expired. Please reload the page.