---
tags: LeetCode
---

# 70. Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a **positive integer**.

Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:
Input: 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
---
輸入範本如下

class Solution {
    public int ClimbStairs(int n) {

    }
}

### 直覺想法
我以前寫黃子嘉的線性代數的時候 , 好像解過這個題目ㄟ. = =
一次限制你只能走一步或是兩步 , 你有 n 階層的樓梯要走.
以 F(n) 表示走完 n 階層的樓梯的方法數量.
F(1) 表示走完 1 階層樓梯的數量.
F(1) = 1
F(2) 表示走完 2 階層樓梯的數量.
F(2) = 2
F(3) 表示走完 3 階層樓梯的數量.
題目限制你只能走一步或是兩步 , 因此若你先走一步 , 那你剩下的樓梯是兩階層 , 若你先走兩步 , 那你剩下的樓梯是一階層 , 因此
F(3) = F(2) + F(1) = 2 + 1
F(3) = 3
同理 , 故 n 階層的公式如下
F(n) = F(n-1) + F(n-2)

另外題目限制 n 為 positive integer , 故 n > 0

// 使用遞迴的寫法會發生 Time Limit Exceeded
public int ClimbStairs(int n)
{
    if (n == 1) return 1;
    if (n == 2) return 2;
    return ClimbStairs(n - 1) + ClimbStairs(n - 2);
}

40 ms	14.9 MB
You are here!
Your runtime beats 67.80 % of csharp submission
// 改用迴圈
public int ClimbStairs(int n)
{
     if (n == 0) return 1;
     // 已知 n == 1 || n == 2 的結果 , 故直接回傳結果
     if (n == 1 || n == 2) return n;

     // 從 n == 1 || n == 2 的結果開始計算 n >= 3 的結果.
     int left = 1, right = 2;
     for (int step = 3; step < n; step++)
     {
          int temp = left + right;
          left = right;
          right = temp;
     }
     return left + right;
}

36 ms	14.7 MB
You are here!
Your runtime beats 93.60 % of csharp submissions.
// 沒什麼意義. 只是為了減少每一筆測資都必須判斷 n == 0 以及 n == 1 || n == 2 的動作
// 從 F(0) = 1 開始
public int ClimbStairs(int n)
{
    int left = 1, right = 1, result = 1;
    for (int step = 1; step < n; step++)
    {
        result = left + right;
        left = right;
        right = result;
    }
    return result;
}

32 ms	14.9 MB
You are here!
Your runtime beats 99.32 % of csharp submissions.
// 以前寫題目時候 , 使用生成函數還是啥方式產生的公式.
public int ClimbStairs(int n)
{
    return (int)((Math.Pow((1 + Math.Sqrt(5)) / 2, n + 1) - Math.Pow((1 - Math.Sqrt(5)) / 2, n + 1)) / Math.Sqrt(5));
}

### Thank you!

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: