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
            }
        }
    }
}