Min Cost to Climb Stairs
Last updated
Last updated
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
We can define as the minimum cost it takes to climb from step . If we start at the first step, the cost is and if we start at the second step, the cost is . Otherwise, for every step , the cost to climb from it is the cost it took to reach it with the cost of leaving the step.
The state caching optimization can be applied here again, given that each state depends only on the previous 2 states.