70. 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
Hint 1:
To reach nth step, what could have been your previous steps? (Think about the step sizes)
題目翻譯
今天有 n
個階梯,然後可以一次採 1 階或 2 階。計算在 n
個階梯之後,可以有幾種登階的可能性
解法解析
恩,很簡單就是一個費氏數列。差別的地方在於,最後的結果要怎麼儲存,可以使用一個陣列去儲存每次的結果,但是這樣就會花費一個陣列的記憶體空間。覺得最後的方式還是只使用一個變數儲存最後的值就好了。不變 Time complexity 的情況下,有最少的 Space complexity。
程式範例
Python
class Solution:
def climbStairs(self, n: int) -> int:
a, b = 1, 1
for _ in range(n):
a, b = b, a + b
return a
JavaScript
/**
* @param {number} n
* @return {number}
*/
var climbStairs = function (n) {
if (n < 2) {
return n;
}
let first = 1;
let second = 2;
for (let i = 3; i <= n; i++) {
const third = first + second;
first = second;
second = third;
}
return second;
};
Go
func climbStairs(n int) int {
if n <= 2 {
return n
}
n1, n2 := 1, 2
for i := 3; i <= n; i++ {
n2, n1 = n1+n2, n2
}
return n2
}
Swift
class Solution {
func climbStairs(_ n: Int) -> Int {
if n < 3 { return n }
var cur = 2
var pre = 1
for i in 3...n {
let temp = pre
pre = cur
cur = cur + temp
}
return cur
}
}
Kotlin
class Solution {
fun climbStairs(n: Int): Int {
return when {
n < 2 -> n
else -> {
var first = 1
var second = 2
for (i in 3..n) {
val temp = first + second
first = second
second = temp
}
second
}
}
}
}