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 Example 1: Input: n = 3 Output: 3
Explanation:
1) 1, 1, 1
2) 1, 2
3) 2, 1
total 3.
Example 2: Input: n = 1 Output: 1
Explanation:
only 1 way.
from functools import lru_cache
class Solution:
"""
@param n: An integer
@return: An integer
"""
@lru_cache(None)
def climbStairs(self, n):
if n <= 3:
return n
return self.climbStairs(n-1) + self.climbStairs(n-2)