# LeetCode Solution, Easy, 70. Climbing Stairs

# [70. Climbing Stairs](https://leetcode.com/problems/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

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

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

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

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

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