LeetCode：(Python)Climbing Stairs

題目連結: https://leetcode.com/problems/climbing-stairs/

題意說明:

有一個長度為 n的梯子，可以一次爬1步或一次爬2步，給定 n，請問總共有幾種爬法?

初始想法

可以用遞迴解，跟費波納契數列很像

• 如果只剩2步，回傳2，因為只剩一次走2步或分兩次走1步兩種可能
• 如果只剩1步，回傳1，因為只剩一次走1步這一種可能
• 如果剩超過3步，可以分成接下來要走1步或走2步兩條路

class Solution:
    def climbStairs(self, n: int) -> int:
        def climb(n):
                
            if n == 2:
                return 2
            if n== 1:
                return 1
            return climb(n-1)+climb(n-2)
        return climb(n)

然後就跑到超時了 XD 難得我用 Functional Programming的做法餒!

反思

嘗試改寫成迴圈

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        
        result = 0
        num1 = 1
        num2 = 2
        for num in range(n-2):
            result = num1 + num2
            num1 = num2
            num2 =result

        return result

還是很慘餒 . . .

最後是可以再優化變數的更新，利用 Python3的技巧

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        
        num1 = 1
        num2 = 2
        for num in range(n-2):
            num1, num2 = num2, num1+num2

        return num2

但一樣的慢，我看其他人的做法也差不多 . . .