climbing-stairs.py

"""
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:

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
"""

def climbStairs(n):
    """
    :type n: int
    :rtype: int
    """
    def compute(n, mem):
        if n < 0:
            return 0
        if n <= 1:
            return 1

        if n in mem:
            return mem[n]


        mem[n] = compute(n-1, mem) + compute(n-2, mem)
        return mem[n]

    return compute(n, {})