0070. Climbing Stairs - chasel2361/leetcode GitHub Wiki

You are climbing a stair case. It takes n steps to reach to the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.

Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

這其實是排列組合問題吧XDDDD

這個問題應該也可以用動態規劃來解

問題一：總共有幾個 2 跟 1 的組合

問題二：每個組合有幾種走法

這兩個問題合在一起就是最終的答案

首先，總共最多可以有 n//2 個 2 ，每少一個 2 就會多兩個 1

而每種組合的走法可以引用排列組合的"不盡相異物直線排列"理論，可以得知有r種n個物品時，這些物品共有 種排列法

所以每組的走法有 n!/n_2!n_1! 種，總共的組數可以使用計數器來達成

[1] 先判斷輸入值是否被 2 整除
[2] 若否，計算走法時需要多加一個 1

class Solution:
    def climbStairs(self, n: int) -> int:
        num_2 = n // 2
        count = 0
        i = 0
        if n % 2 == 1:  # [1]
            while num_2 >= 0:
                up = self.factorial(num_2 + i*2 + 1)  # [2]
                do = self.factorial(num_2) * self.factorial(i*2 + 1)  # [2]
                count += (up / do)
                num_2 -= 1
                i += 1
        else:  # [1]
            while num_2 >= 0:
                up = self.factorial(num_2 + i*2)
                do = self.factorial(num_2) * self.factorial(i*2)
                count += (up / do)
                num_2 -= 1
                i += 1
        return int(count)
        
    def factorial(self, n):
        res = 1
        while n > 1:
            res *= n
            n -= 1
        return res

這個解法的時間複雜度是O(N)，空間複雜度是O(1)

---

寫完之後發現雨蕭大大有更快的解法，他的概念是來看看能不能找到相互之間的關係

如果要走到第 n 階的話，就需要知道走到第 n - 1 階以及第 n - 2 階的組數 (因為只有一次走一階跟一次走兩階兩種走法) ，兩者相加即為答案。同樣的，要走到第 n - 1 階，就需要知道走到第 n - 2 階以及第 n - 3 階的組數。

以此類推，最後需要知道走到第 1 階以及第 2 階所需要的組數，其分別為 1 組及 2 組。

由此可知

走到第 3 階的組數 = 1 + 2 = 3

走到第 4 階的組數 = 3 + 2 = 5

[1] 使用 s1, s2 相互相加以減少記憶體需求

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
            
        s1, s2 = 1, 2
        for _ in range(n - 2):
            s1, s2 = s2, s1 + s2  # [1]
        return s2

這個解法的時間複雜度依舊是O(N)，但程式結構簡單很多，速度可以更快。空間複雜度是O(1)