You are given an integer array cost where cost[i] is the cost of ith 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 1:
Input: cost = [10,15,20]
Output: 15
Explanation: Cheapest is: start on cost[1], pay that cost, and go to the top.
Example 2:
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: Cheapest is: start on cost[0], and only step on 1s, skipping cost[3].
Constraints:
2 <= cost.length <= 10000 <= cost[i] <= 999Min Cost Climbing Stairs - LeetCode
Before we begin, let's clear up some of the confusion surrounding the problem statement.
The "top of the floor" does not refer to the final index of costs. We actually need to "arrive" beyond the array's bounds.
Let's look at an example costs = [0,1,2,3,4,5]. Since we can take 1 or 2 steps at a time, we need to reach either step 4 or step 5 (0-indexed), and then pay the respective cost to reach the top. For this example, to reach step 4 optimally would cost 2 by taking path 0 --> 2 --> 4 (we're not counting the cost of step 4 yet since we are only talking about reaching the step right now). To reach step 5 optimally would cost 4 by taking path 1 --> 3 --> 5.
Now, imagine that before we started the problem, somebody came up to us and said "to optimally reach step 4 costs 2 and to optimally reach step 5 costs 4." Well, then the problem is trivial - the answer is the minimum of 2 + cost[4] = 6 and 4 + cost[5] = 9. The only reason this was so easy was because we already knew the cost to reach steps 4 and 5.
So how do we find the minimum cost to reach step 4 or step 5? Well, you might notice that it's the exact same problem, just with a smaller input. For example, finding the minimum cost to reach step 4 is like solving the original problem with input [0,1,2,3] (step 4 is the "top of the floor" now). To solve this subproblem, we need to find the minimum cost to reach steps 2 and 3, which requires us to answer the original problem for inputs [0,1] and [0,1,2].