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 

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