A staircase has cost.length steps, numbered from 0. Stepping off step i costs cost[i]: you pay it, then move up either one step or two steps.
You may begin on step 0 or on step 1 for free. The top is the spot just above the last step, at position cost.length; reaching it ends the climb and costs nothing more.
Return the smallest total you can pay to get from the bottom to the top.
Begin on step 1 and pay 2 to jump two steps to step 3. Pay 3 there and jump two more, which lands on the top. Steps 0, 2 and 4 are never paid for.
No move covers more than two steps, so every route stands on step 1 or step 2, and on step 4 or step 5: at least 9 + 9 is unavoidable. Begin on step 1 (9), jump to step 3 (1), jump to step 5 (9), and jump to the top.
From either step, a single move of the right size reaches the top.
Constraints
2 <= cost.length <= 10000 <= cost[i] <= 999Work out, for each position, the cheapest way to stand on it. You can reach position i only from i − 1 or i − 2, so its best cost depends only on those two.
5