# Leetcode 70. Climbing Stairs

## 題解

### 遞迴 (TLE)

class Solution:
    def climbStairs(self, n: int) -> int:
        # Time complexity: O(2^n)
        # Space complexity: O(n) Recrion stack space
        output = 0
        def recr(n: int):
            nonlocal output
            if n <= 1:
                output += 1
                return
            
            recr(n - 1)
            recr(n - 2)
        
        recr(n)
        return output

### 哈希表

DP Bottom up 利用哈希表紀錄已走過的分支，藉此剪枝，達到 O(n) 複雜度

class Solution:
    def climbStairs(self, n: int) -> int:
        # Time complexity: O(n)
        # Space complexity: O(1)
        memo = {}
        def recr(n: int):
            if n <= 1:
                return 1
            if n not in memo:
                memo[n] = recr(n - 1) + recr(n - 2)
            return memo[n]
        return recr(n)

### Space complexity 優化

藉由哈希表的解法可以得知，每次剪枝會使用到的其他 n 只會有前兩個狀態，所以可以把空間複雜度優化到 O(1)

class Solution:
    def climbStairs(self, n: int) -> int:
        # Time complexity: O(n)
        # Space complexity: O(1)
        if n <= 1:
            return 1
        n1 = 1
        n2 = 1
        for i in range(2, n+1):
            temp = n2
            n2 = n1 + n2
            n1 = temp
        return n2