#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?

#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

## brutal force: O(2**n)
def climbStairs(n):
    if n<=0: return 0
    if n==1: return 1
    if n==2: return 2
    return climbStairs(n-1)+climbStairs(n-2)



## dyamic programming
def climbStairs(n):
    dp= [None]* (n+1)
    dp[0], dp[1]=1,1
    for i in range(2, n+1):
        print(i)
        dp[i]=dp[i-1]+dp[i-2]
    return dp[n]
climbStairs(38)