Solutions

# At each step, the cost of climbing is cost(s-1) + cost(s-2). Base cases 0, 1. Recursion or iterative dp.
# dp

# Brute force recursion - O(2^n) time, O(n) space (recursion stack)
def minCostClimbingStairs(cost: list[int]) -> int:
    def dfs(i):
        if i >= len(cost):
            return 0
        return cost[i] + min(dfs(i + 1), dfs(i + 2))

    return min(dfs(0), dfs(1))


# Recursion with memoization - O(n) time, O(n) space (memoization + recursion stack)
def minCostClimbingStairs(cost: list[int]) -> int:
    cache = {}

    def dfs(i):
        if i >= len(cost):
            return 0
        if i in cache:
            return cache[i]
        cache[i] = cost[i] + min(dfs(i + 1), dfs(i + 2))
        return cache[i]

    return min(dfs(0), dfs(1))


# Iterative bottom-up dp - O(n) time, O(n) space
def minCostClimbingStairs(cost: list[int]) -> int:
    n = len(cost)
    dp = [0] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = min(dp[i-1] + cost[i-1],
                    dp[i-2] + cost[i-2])
    return dp[n]