70. Climbing Stairs

def climbing_stairs(n):
    """Recursive approach with memoization."""
    def helper(n):
        nonlocal memo

        if n in memo:
            return memo[n]
        else:
            result = helper(n-1) + helper(n-2)
            memo[n] = result
            return result

    memo = {0: 0, 1: 1, 2: 2}
    return helper(n)

def climbing_stairs(n):
    """Using tail recursion.
    see generalization on tail recursion here:
    https://nbviewer.jupyter.org/github/adrien-perelloyb/leetcode/blob/main/lessons/recursion.ipynb
    """
    def go(n, acc1, acc2):
        """tail recursive function"""
        if n < 2:
            return acc1
        return go(n-1, acc2, acc1+acc2)

    return go(n, 1, 2)

def climbing_stairs(n):
    """ Dynamic Programming approach
    Time Complexity: O(n)
    Space Complexity: 0(n)
    """
    if n == 0 or n == 1 or n == 2:
        return n
    dp = [0, 1, 2]
    for i in range(3, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])
    return dp[n]

# The key intuition to solve the problem is that given a number of stairs n,
# if we know the number ways to get to the points [n-1] and [n-2] (denoted as n1 and n2)
# then the total ways to get to the point [n] is n1 + n2.
# Because from the [n-1] point, we can take one single step to reach [n],
# and from the [n-2] point, we could take two steps to get there.

def climbing_stairs(n):
    """Same as above but with Space Complexity: 0(1)."""
    curr, prev = 1, 0
    for _ in range(n):
        curr, prev = curr + prev, curr
    return curr

def climbStairs(n):
    '''Time Complexity O(logn) thanks to hard encoded matrix power computation'''
    def matrix_prod(M, K):
        a = M[0][0] * K[0][0] + M[0][1] * K[1][0]
        b = M[0][0] * K[0][1] + M[0][1] * K[1][1]
        c = M[1][0] * K[0][0] + M[1][1] * K[1][0]
        d = M[1][0] * K[0][1] + M[1][1] * K[1][1]
        return [[a, b], [c, d]]
        
    def power(M, n):
        if n == 0:
            return [[1, 0], [0, 1]]
        if n == 1:
            return M
        half = power(M, n//2)
        ret = matrix_prod(half, half)
        if n % 2 == 1:
            ret = matrix_prod(ret, M)
        return ret
    
    M = [[1, 1], [1, 0]]
    [[a, b], [c, d]] = power(M, n)
    return a