LC746 - Min Cost Climbing Stairs

Problem

You are given an integer array cost where cost[i] is the cost of the i-th step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index 0, or the step with index 1. Return the minimum cost to reach the top of the floor

Example

Input: cost = [10, 15, 20]

Output: 15

Explanation: Cheapest is to start on cost[1], pay that cost, and reach the top.

Solution

Naive

Fill out all the edges to each node on the decision tree, which costs $O(2^n)$. Similar to the brute force solution of Climbing Stairs, except we count cost instead of steps. Then sum up the edges and return the minimum cost solution.

Dynamic Programming

Incrementally fill out the minimum cost to reach the end from a particular step, going from the top to bottom. This works because the min cost of each step is dependent on the min cost of the next two steps.

In theory, we don’t need to rewrite the array and only need to keep two variables, but this is the easiest/most intuitive way to code for me.

Time complexity of this solution is $O(n)$ and space complexity is $O(1)$, since we don’t use any extra space save for temporary variables.

def minCostClimbingStairs(self, cost: List[int]) -> int:
    # Start from third last element
    ptr = len(cost)-1
    # Calculate total cost to end from current step
    while True:
        curCost = cost[ptr]
        
        # Get cost of jump 1 and jump 2, if n.e., set to 0
        if ptr+1 > (len(cost)-1):
            cost_jump1 = 0
        else:
            cost_jump1 = cost[ptr + 1]
        
        if ptr+2 > (len(cost)-1):
            cost_jump2 = 0
        else:
            cost_jump2 = cost[ptr + 2]

        # Compare jump 1 against jump 2 and return 
        if cost_jump1 < cost_jump2:
            cost[ptr] = curCost + cost_jump1
        else:
            cost[ptr] = curCost + cost_jump2
        
        # decrement pointer and break if end is reached
        ptr = ptr - 1
        if ptr < 0:
            break

    return min(cost[0], cost[1])