LeetCode 70. Climbing Stairs [Easy] [C++] 解題筆記

這題是很簡單又經典的 DP 題目，一定要會!

題目給定一正整數 n 表示有 n 級樓梯，爬樓梯時一次只能往上爬一級或二級，求爬上 n 級樓梯所有的方法數。

EX:

        Input: 2

Ans: 2,   一共兩種爬法，一次往上爬一級爬兩次( 1 steps + 1 steps)，直接往上爬兩級( 2 steps)。

想法:

        這題是很基本的 DP 題，爬到第 n 級樓梯的方法數會等同於爬到 n - 1 級與 n - 2 級方法數的總和。另外這邊可以發現到要求第 n 級樓梯的方法數只須要知道 n - 1 和 n - 2 級的方法數，因此除了用一個一維陣列紀錄每級的方法數外，也可以只使用三個變數分別紀錄 n - 1, n - 2, 與 n 的方法數並不斷更新即可。

Time Complexity: O(n) time, O(n)/O(1) space

完整程式碼:

O(n) space:

class Solution {

public:

    int climbStairs(int n) {

        if (n < 2) { return 1; }

        vector<int> dp(n+1, 0); 

        dp.at(0) = 1;

        dp.at(1) = 1;

        for (int i = 2; i < dp.size(); i++) {

            dp.at(i) = dp.at(i-1) + dp.at(i-2);

        }   

            

        return dp.at(n);

    }   

};

O(1) space:

class Solution {

public:

    int climbStairs(int n) {

        if (n < 2) { return 1; }

        int base = 1;

        int first = 1;

        int cur = 0;

        for (int i = 2; i < n + 1; i++) {

            cur = base + first;

            base = first;

            first = cur;

        }

        

        return cur;

    }

};