runtime 0 ms, beats 100% of cpp submissions
O(n) solution with explanation

tags: dp

Climbing Stairs

📖 description

給定一個數字 x ，輸出 f(x) ，其中 f(x) 表示第 x 個 Fibonacci 數。

ex.
    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

🧠 solution

Fibonacci 數列的計算方法是 f(x) = f(x-1) + f(x-2) ，於是只需要維護數列最後三項即可，並實際模擬數列的計算。

⏳ time complexity

模擬從 1 ~ n 的結果，時間複雜度 O(n)
總時間複雜度 O(n)

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int climbStairs(int n) {
        int p0 = 0,p1 = 1,p2 = 1;   // 初始化成前三項的結果
        if(n<=2){
            return n;
        }
        for(int i=2;i<=n;i++){
            p0 = p1;    // 更新第一個數
            p1 = p2;    // 更新第二個數
            p2 = p0+p1; // 計算結果
        }
        return p2;
    }
};