70. Climbing Stairs

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

Solutions

1. DP-迭代自底向上

　　注意循环次数是 n-1，不是 n-2。

# Time Complexity: O(n)
# Space Complexity: O(1)
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 0:
            return 0
        if n == 1:
            return 1
        fn = 0
        fn_2 = 1
        fn_1 = 1
        for i in range(n-1):
            fn = fn_2 + fn_1
            fn_2 = fn_1
            fn_1 = fn
        return fn
# Runtime: 40 ms, faster than 27.63% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 13.9 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.

2. DP-递归自顶向下

　　注意存储：

# Time Complexity: O(n)
# Space Complexity: O(n)
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 0:
            return 0
        if n == 1:
            return 1
        self.memo = [0 for _ in range(n+1)]
        self.memo[0] = 1
        self.memo[1] = 1
        self.fibonacci(n)
        return self.memo[-1]
        
    
    def fibonacci(self, n: int) -> int:
        if n == 0 or n == 1:
            return 1
        
        if self.memo[n-1] == 0:
            self.memo[n-1] = self.fibonacci(n-1)
        
        if self.memo[n-2] == 0:
            self.memo[n-2] = self.fibonacci(n-2)
        
        self.memo[n] = self.memo[n-1] + self.memo[n-2]
        return self.memo[n]
        
# Runtime: 32 ms, faster than 89.69% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 13.9 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.

　　不够简洁，做进一步简化：

# Time Complexity: O(n)
# Space Complexity: O(n)
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1
        self.memo = [0 for _ in range(n+1)]
        self.memo[0] = 1
        self.memo[1] = 1
        return self.fibonacci(n)
        
    
    def fibonacci(self, n: int) -> int:
        if self.memo[n] == 0:
            self.memo[n] = self.fibonacci(n-1) + self.fibonacci(n-2)
        return self.memo[n]
        
# Runtime: 32 ms, faster than 89.69% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 13.9 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.

　　当然还可以用哈希表做存储，查找起来也相对较快，不要用 List 查找！

# Time Complexity: O(n)
# Space Complexity: O(n)
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1
        self.memo = {0: 1, 1: 1}
        return self.fibonacci(n)
        
    
    def fibonacci(self, n: int) -> int:
        if n in self.memo:
            return self.memo[n]
        
        self.memo[n-1] = self.fibonacci(n-1)
        self.memo[n-2] = self.fibonacci(n-2)
        self.memo[n] = self.memo[n-1] + self.memo[n-2]
        
        return self.memo[n]
# Runtime: 36 ms, faster than 67.28% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 14 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.

References

70. Climbing Stairs