README.md

title	subtitle	date	lastmod	draft	author	authorLink	description	license	images	tags	categories	featuredImage	featuredImagePreview	hiddenFromHomePage	hiddenFromSearch	twemoji	lightgallery	ruby	fraction	fontawesome	linkToMarkdown	rssFullText	toc	code	math	mapbox	share	comment	library	seo
746. Min Cost Climbing Stairs	https://leetcode.com/problems/min-cost-climbing-stairs/	2023-12-29 16:24:00 +0800	2023-12-29 16:24:00 +0800	false	Kimi.Tsai	https://kimi0230.github.io/	0746.Min-Cost-Climbing-Stairs			LeetCode Go Easy Min Cost Climbing Stairs	LeetCode			false	false	false	true	true	true	true	false	false	enable auto true true	copy maxShownLines true 200	enable		enable true	enable true	css js	images

746. Min Cost Climbing Stairs

題目

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: You will start at index 1.

• Pay 15 and climb two steps to reach the top. The total cost is 15. Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1] Output: 6 Explanation: You will start at index 0.

• Pay 1 and climb two steps to reach index 2.
• Pay 1 and climb two steps to reach index 4.
• Pay 1 and climb two steps to reach index 6.
• Pay 1 and climb one step to reach index 7.
• Pay 1 and climb two steps to reach index 9.
• Pay 1 and climb one step to reach the top. The total cost is 6.

Constraints:

2 <= cost.length <= 1000 0 <= cost[i] <= 999

題目大意

陣列的每個索引做為一個階梯，第 i 個階梯對應著一個非負數的體力花費值 cost[i] （索引從 0 開始）。 每當你爬上一個階梯你都要花費對應的體力花費值，然後你可以選擇繼續爬一個階梯或者爬兩個階梯。 您需要找到達到樓層頂部的最低花費。 在開始時，你可以選擇從索引為 0 或 1 的元素作為初始階梯。

解題思路

cur 變數存儲從第 i-2 步到達第 i 步的最小花費。 last 變數存儲從第 i-1 步到達第 i 步的最小花費。 在每次迭代中，函數都會比較 cur 和 last 變數的值，並選擇較小的那個存儲在 cur 變數中。 在迭代結束時，last 變數將存儲爬完所有樓梯的最小花費。

cost := []int{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}

迭代	cur	last
2	0	1
3	1	2
4	2	2
5	2	3
6	3	3
7	3	4
8	4	4
9	4	5
10	5	6

Big O

時間複雜 : O(n) 空間複雜 : O(1)

來源

• https://leetcode.com/problems/min-cost-climbing-stairs/
• https://leetcode.cn/problems/min-cost-climbing-stairs/
• https://books.halfrost.com/leetcode/ChapterFour/0700~0799/0746.Min-Cost-Climbing-Stairs/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0746.Min-Cost-Climbing-Stairs/main.go

package mincostclimbingstairs

// 時間複雜 O(n), 空間複雜 O(1)
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-1], dp[i-2])
	}
	return min(dp[len(cost)-2], dp[len(cost)-1])
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

// 時間複雜 O(n), 空間複雜 O(1)
// 優化
// 使用了兩個變數cur和last，
// cur 變數存儲從第 i-2 步到達第 i 步的最小花費。
// last 變數存儲從第 i-1 步到達第 i 步的最小花費。
// 比較兩種選擇的花費：
// 從第2階開始（i := 2），一直迭代到最後一階（i < len(cost)+1）。
// 在每一步驟中：
// 比較兩種選擇的花費：
//
//	選擇從上一階跳到當前階的花費：last + cost[i-1]
//	選擇從上上階跳到當前階的花費：cur + cost[i-2]
//
// 選擇花費較小的方案：
//
//	如果 last + cost[i-1] 更小，則將 last 的值更新為 cur + cost[i-2]，並將 cur 的值更新為 last（即上一步的最小花費）。
//	否則，將 last 的值更新為 last + cost[i-1]，並將 cur 的值更新為 last（即上一步的最小花費）。
func MinCostClimbingStairsOptimize(cost []int) int {
	var cur, last int
	for i := 2; i < len(cost)+1; i++ {
		// 選擇從上一階跳到當前階的花費：last + cost[i-1]
		// 選擇從上上階跳到當前階的花費：cur + cost[i-2]
		if last+cost[i-1] > cur+cost[i-2] {
			cur, last = last, cur+cost[i-2]
		} else {
			cur, last = last, last+cost[i-1]
		}
		// fmt.Printf("%-d | %-d | %-d\n", i, cur, last)
	}
	return last
}

Benchmark

goos: darwin
goarch: amd64
pkg: LeetcodeGolang/Leetcode/0746.Min-Cost-Climbing-Stairs
cpu: Intel(R) Core(TM) i5-6400 CPU @ 2.70GHz
BenchmarkMinCostClimbingStairs-4                36693742                30.17 ns/op           24 B/op          1 allocs/op
BenchmarkMinCostClimbingStairsOptimize-4        405489464                3.091 ns/op           0 B/op          0 allocs/op
PASS
ok      LeetcodeGolang/Leetcode/0746.Min-Cost-Climbing-Stairs   2.713s