題目

  • 題目連結
  • 目標函式 : climbStairs(n)
    • Input : n: int
    • Output : int

解題概念

  • 題意 :
    • 現在要爬樓梯，題目給定需要 n 步抵達樓上
    • 每次可以跨一階或跨兩階
    • 需要回傳總共有多少種方式上樓

我的寫法

  • 想法 : 這題也是演算法很經典的一題，我這裡簡單解釋它的想法，詳細的解題方式可參考 LeetCode #70 Climbing Stairs 解題思路及翻譯
    • 首先可從遞迴的概念下手，climbStairs(n) 總共可分為兩類 :
      1. 走一階 + climbStairs(n - 1)
      2. 走二階 + climbStairs(n - 2)
    • 因此，可列出遞迴式 : climbStairs(n) = climbStairs(n - 1) + climbStairs(n - 2)
    • 而此遞迴式就是經典的 費式數列，因此我就直接使用費式數列的解法來解這題
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    if n == 0 :
            return 0
        elif n == 1:
            return 1
        else:

            a,b,c = 0, 1, 1
            for i in range(2, n+1):
                a = b
                b = c
                c = a + b
            return c
  • 成效 :
    • Time Complexity : $\color{DB4D6D}{O(n)}$
    • Runtime: 14 ms (faster than 73.29%)
    • Memory Usage: 13.3 MB (more than 33.50%)

解答 or 其他優秀寫法

  • 想法 : 也有完全 Recursion 的寫法，但隨著 n 增加，更容易找至 Time Limitation Exceeded 的狀況發生