70. Climbing Stairs

Question: Climbing Stairs

Solution1

爬到第 n 階的方法 = 爬到 n - 1 階的方法 + 爬到 n - 2 階的方法

因為單純寫遞迴會超時

class Solution:

def climbStairs(self, n: int) -> int:

def s(n):

if n == 0:

return 0

elif n == 1:

return 1

elif n == 2:

return 2

return s(n - 1) + s(n - 2)

return s(n)

代表重複計算的部分要抽出來，另外存，因此用一個 hash map 改寫如下後，就可以囉！

from collections import defaultdict

class Solution:

def climbStairs(self, n: int) -> int:

s_method = defaultdict(int)

def s(n):

if n == 0:

return 0

elif n == 1:

return 1

elif n == 2:

return 2

s1 = s_method[n - 1] if n - 1 in s_method else s(n - 1)

s2 = s_method[n - 2] if n - 2 in s_method else s(n - 2)

method = s1 + s2

s_method[n] = method

return method

return s(n)

Solution2

• 爬到第 1 階的方式有 1 種：0 → 1 = 1
• 爬到第 2 階的方式有 2 種：0 → 1 → 1, 0 → 2 = 2
• 爬到第 3 階的方式有 3 種： 爬到第 1 階後一次走兩格, 爬到第二階後一次走一格 = 第一階方法 + 第二階方法 = 1 + 2 = 3
• 爬到第 4 階的方式有 5 種：爬到第 2 階後一次走兩格，爬到第 3 階後一次走一格 = 第二階方法 + 第三階方法 = 2 + 3 = 5
• 依此類推
• 用 list 紀錄每一階到達的方法，依序算出要到達的階層

class Solution:

def climbStairs(self, n: int) -> int:

stairs_method = [1, 2]

for i in range(2, n):

stairs_method.append(stairs_method[i - 1] + stairs_method[i - 2])

return stairs_method[n - 1]

改良上個方式，只需要存取最近的兩個方法就好，讓空間複雜度降低

class Solution:
    def climbStairs(self, n: int) -> int:
        one, two = 1, 1
        for i in range(n - 1):
            method = one + two
            one, two = two, method
        return two

Video Solution