pylist

111. 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 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.

solution

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)