70.Climbing Stairs
===

###### tags: `Easy`,`Math`,`Memoization`,`DP`

[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

### 解答
#### C++

class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 0;
        while (n--) {
            b = (a += b) - b;
        }
        return a;
    }
};

> [name=Yen-Chi Chen][time=Mon, Dec 12]

#### Javascript

function climbStairs(n) {
  const fib = [1, 1, 2, 3];
  for (let i = 4; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }

  return fib[n];
}

Time: $O(n)$
Space: $O(n)$

function climbStairs(n) {
  if (n < 4) return n;
  let a = 1;
  let b = 2;
  let result = 0;
  for (let i = 3; i <= n; i++) {
    result = a + b;
    a = b;
    b = result;
  }

  return result;
}

Time: $O(n)$
Space: $O(1)$

> [name=Marsgoat][time= Dec 12, 2022]

#### Python

class Solution:
    def climbStairs(self, n: int) -> int:
        fn, fnn, fnnn = 1, 2, 0
        for _ in range(3, n+1):
            fnnn = fn + fnn
            fn, fnn = fnn, fnnn

        return fnnn if n > 2 else (fnn if n == 2 else fn)

> [name=Kobe][time=Mon, Dec 12]

#### C#

public class Solution {
    public int ClimbStairs(int n) {
        if (n <= 2) return n;

        int a = 1;
        int b = 2;
        
        for (int i = 3; i <= n; i++) {
            int temp = b; 
            b = a + b;
            a = temp;
        }
        
        return b;
    }
}

> [name=Jim][time=Mon, Dec 12]
### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)