LeetCode 70 – Python 3 (Week 2 – 03)

There are two ways to climb n steps: (1) climb n-1 steps + climb one step (2) climb n-2 steps + climb two step. The basic idea is that the ways for n steps is the sum of ways for n-1 steps and n-2 steps. If we use recurrence, the time complexity is high. Thus, we want to store the previous results in an array or a dictionary. But we just need return the ways for n steps which is only dependent on the ways for n-1 and n-2 steps. So, only two integer variables are needed. The link below explain all methods very clear:

https://leetcode.com/problems/climbing-stairs/discuss/163347/Python-3000DP-or-tm

Solution 1: time complexity O(n), space complexity O(1)

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

        
        if n == 1: return 1
        previous, current = 1, 2 #n=1 n=2
        for _ in range(2, n):
            previous, current = current, previous + current #n-2 and n-1 starirs to n-1 and n stairs.
        return current