70 Climbing Stairs

1. Description

You are climbing a staircase. It takes n steps to reach the top. Each time you can either clibm 1 or 2 steps. In how many distinct ways can you climb to the top?

 

constraints :

• 1 <= n <= 45

2. Algorithms

Let's see the example 1 to 5.If n = 1, then result will be 1. If n = 2, then result will be 2. If n = 3, then result will be 3, If n = 4, then resul will be 5.

n	F(n)	DP
1	1	F(1)
2	2	F(2)
3	3	F(1) + F(2)
4	5	F(2) + F(3)
5	8	F(3) + F(4)

The result of n is constisted of sum of n-1 and n-2. We will apply dynamic programming to this problem.

1. If n is 1 or 2, then the result will be n.
2. If n is bigger then 2, then the result will be sum of results of n-1 and n-2.

Firstly, we will initialize variable first, second as when we can get n = 1, n = 2. After than, we will update first and second as second and first + second. By doing this, first store previous results of f(n-2) and second store previous results of f(n-1).

3. Codes

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2 : 
            return n 
        
        first = 1
        second = 2
        for _ in range(2, n) : 
            first, second = second, first + second 
        return second

4. Conclusion