Min Cost Climbing Stairs
EasyThe problem
cost[i] is the price of stepping off stair i. You may start on stair 0 or stair 1, and from any stair you climb 1 or 2 stairs. The top is one position past the last stair. Return the least total price to reach the top.
- Example 1Input: cost = [10, 15, 20]Output: 15
Start on stair 1, pay 15, and jump 2 stairs to the top.
- Example 2Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]Output: 6
Land on every stair with cost 1 by jumping over the 100s: 1+1+1+1+1+1 = 6.
- 2 ≤ len(cost) ≤ 1,000
- 0 ≤ cost[i] ≤ 999
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Cheapest cost to stand on step i depends on the two steps below it.
The idea
dp[i] = cost[i] + min(dp[i−1], dp[i−2]); the answer is min of the last two.
Target: O(n) time, O(1) space
Go function shape
func minCostClimbingStairs(cost []int) intReference solution
Tested with go test. Try it yourself first, then compare.
// MinCostClimbingStairs: you may start on step 0 or 1; the top is just past the last step.
// State: cost to stand on step i = cost[i] + the cheaper of the two steps you could have come from.
func MinCostClimbingStairs(cost []int) int {
a, b := 0, 0 // cheapest cost to reach the two most recent steps (starting is free)
for i := 2; i <= len(cost); i++ {
a, b = b, min(b+cost[i-1], a+cost[i-2])
}
return b
}