
# LeetCode
# 70
# Easy

# 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

class Solution:
    def climbStairs(self, n: int) -> int:
        '''
        init steps list with base cases 0, 1, 2
        new el = sum of last 2 elements
        append the new el to the list while len(list) <= n
        return list[n]
        '''

        steps = [0,1,2]
        while len(steps) <= n:
            steps.append(steps[-1] + steps[-2])
        return steps[n]
