algos/70.py at main · Kirill-Katz/algos · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# top to bottom approach
#class Solution:
#    def climbStairs(self, n, memo={}):
#        if (n == 0):
#            return 1
#
#        if (memo.get(n) is not None):
#            return memo.get(n)
#
#        n2 = 0
#        n1 = self.climbStairs(n - 1, memo)
#        if (n - 2 >= 0):
#            n2 = self.climbStairs(n - 2, memo)
#
#        memo[n] = n1 + n2
#        return n1 + n2

# bottom to top approach
class Solution:
    def climbStairs(self, n):
        grid = [1, 2]

        if n == 1: return 1
        if n == 2: return 2

        temp = 0
        for _ in range(3, n + 1):
            temp = grid[1] + grid[0]
            grid[0] = grid[1]
            grid[1] = temp

        return temp


solution = Solution()
print(solution.climbStairs(1))
print(solution.climbStairs(2))
print(solution.climbStairs(3))
print(solution.climbStairs(4))
print(solution.climbStairs(5))
print(solution.climbStairs(6))