746. Min Cost Climbing Stairs #

Problem #

On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

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].

Note:

cost will have a length in the range [2, 1000].
Every cost[i] will be an integer in the range [0, 999].

Problem Summary #

Each index of the array is treated as a stair, and the i-th stair corresponds to a non-negative physical cost value cost[i] (indexed from 0). Every time you climb onto a stair, you must pay the corresponding physical cost value, and then you can choose to continue climbing one stair or two stairs. You need to find the minimum cost to reach the top of the floor. At the start, you can choose the element with index 0 or 1 as the initial stair.

Solution Approach #

This problem can be considered an enhanced version of problem 70. It is still a stair-climbing problem, and the solution approach is also DP. On top of the stair-climbing problem, a new condition is added: each stair has a cost, and the question asks what the minimum cost is to reach the final floor.
dp[i] represents the minimum cost to reach the n-th floor. The state transition equation is dp[i] = cost[i] + min(dp[i-2], dp[i-1]), and the minimum cost to reach the final n-th floor is min(dp[n-2], dp[n-1]).
Since the cost of each stair is only related to the previous two stairs, only 2 temporary variables are needed for each DP iteration. This can be used to optimize the auxiliary space.

Code #


package leetcode

// Solution 1 DP
func minCostClimbingStairs(cost []int) int {
	dp := make([]int, len(cost))
	dp[0], dp[1] = cost[0], cost[1]
	for i := 2; i < len(cost); i++ {
		dp[i] = cost[i] + min(dp[i-2], dp[i-1])
	}
	return min(dp[len(cost)-2], dp[len(cost)-1])
}

// Solution 2 DP optimize auxiliary space
func minCostClimbingStairs1(cost []int) int {
	var cur, last int
	for i := 2; i < len(cost)+1; i++ {
		if last+cost[i-1] > cur+cost[i-2] {
			cur, last = last, cur+cost[i-2]
		} else {
			cur, last = last, last+cost[i-1]
		}
	}
	return last
}