Min Cost to Climb Stairs


  • 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)={cost(0),n=0cost(1),n=1minā”(dp(nāˆ’1),dp(nāˆ’2))+cost(n)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)dp(n) as the minimum cost it takes to climb from step nn. If we start at the first step, the cost is cost(0)cost(0) and if we start at the second step, the cost is cost(1)cost(1). Otherwise, for every step nn, the cost to climb from it is the cost it took to reach it with the cost of leaving the step.


The nn 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)

Last updated