min-cost-to-climb-stairs.md

Min Cost to Climb Stairs

Observations

• On each step n, we must incur the cost since we have to decide whether or not to move one or two steps up
• To reach step n, you must move from step n - 1 or step n - 2
• To minimize the cost to reach step n, we need to minimize the cost it takes to reach it

Recurrence relation

$$ dp(n) = \begin{cases} cost(0), n = 0\\ cost(1), n = 1\\ \min(dp(n-1),dp(n-2)) + cost(n) \end{cases} $$

We can define $$dp(n)$$ as the minimum cost it takes to climb from step $$n$$. If we start at the first step, the cost is $$cost(0)$$ and if we start at the second step, the cost is $$cost(1)$$. Otherwise, for every step $$n$$, the cost to climb from it is the cost it took to reach it with the cost of leaving the step.

Bottom-up

The $$n$$ state caching optimization can be applied here again, given that each state depends only on the previous 2 states.

def climb_stairs(costs):
    s1, s2 = costs[0], costs[1]
    for i in range(2, len(costs)):
        s1, s2 = s2, min(s1, s2) + costs[i]
    return min(s1, s2)