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
0070.Climbing Stairs	https://leetcode.com/problems/climbing-stairs/	2023-12-27 16:34:00 +0800	2023-12-27 16:34:00 +0800	false	Kimi.Tsai	https://kimi0230.github.io/	0070.Climbing-Stairs			LeetCode Go Easy Climbing Stairs DP	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

0070.Climbing Stairs

題目

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps Example 2:

Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

1 <= n <= 45

• Accepted: 2.8M
• Submissions: 5.4M
• Acceptance Rate: 52.3%

題目大意

類似 Fibonacci Number

解題思路

• 簡單的 DP，經典的爬樓梯問題. 一個樓梯可以由 n-1 和 n-2 的樓梯爬上來。
• 這一題求解的值就是斐波那契數列。

Big O

時間複雜 : 空間複雜 :

來源

• https://leetcode.com/problems/climbing-stairs/
• https://leetcode.cn/problems/climbing-stairs/
• https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0070.Climbing-Stairs/

解答

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

package climbingstairs

// 時間複雜 O(n), 空間複雜 O(n)
func ClimbStairs(n int) int {
	dp := make([]int, n+1)
	dp[0], dp[1] = 1, 1

	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

func ClimbStairsCache(n int) int {
	dp := make([]int, n+1)
	dp[0], dp[1] = 1, 1

	for i := 2; i <= n; i++ {
		if val := dp[i]; val == 0 {
			dp[i] = dp[i-1] + dp[i-2]
		}
	}
	return dp[n]
}

func ClimbStairsRecursive(n int) int {
	dp := make([]int, n+1)
	// dp[0], dp[1] = 1, 1

	var climbClosure func(n int) int
	climbClosure = func(n int) int {
		if n <= 2 {
			return n
		}
		dp[n] = climbClosure(n-1) + climbClosure(n-2)
		return dp[n]
	}
	return climbClosure(n)
}

Benchmark

goos: darwin
goarch: amd64
pkg: LeetcodeGolang/Leetcode/0070.Climbing-Stairs
cpu: Intel(R) Core(TM) i5-8259U CPU @ 2.30GHz
BenchmarkClimbStairs-8                  10386211               112.1 ns/op           320 B/op          1 allocs/op
BenchmarkClimbStairsCache-8             10184984               118.8 ns/op           320 B/op          1 allocs/op
BenchmarkClimbStairsRecursive-8                4         281980486 ns/op             320 B/op          1 allocs/op
PASS
ok      LeetcodeGolang/Leetcode/0070.Climbing-Stairs    5.591s