Leetcode 70. Climbing Stairs

Climbing Stairs :

爬樓梯，爬到頂要n階。每次可以爬1或2階樓梯，有多少種不同的爬法可以到頂？

Python

利用遞迴求解，爬第 n 階樓梯的方法數」等於「爬上 n−1 階樓梯的方法數量」 + 「爬上 n−2 階樓梯的方法數量」-> S[i] = S[i – 2] + S[i – 1]

class Solution:
    def climbStairs(self, n: int) -> int:
        S = [0, 1, 2]
        for i in range(3, n):
            S[i] = S[i - 2] + S[i - 1]
        return S[n]

class Solution:
    def climbStairs(self, n: int) -> int:
        S = [0, 1, 2]
        if len(S) < n:
            S[n] = climbStairs(n - 2) + climbStairs(n - 1);
        return S[n];

C++

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return 1;
        vector<int> dp(n);
        dp[0] = 1; dp[1] = 2;
        for (int i = 2; i < n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp.back();
    }
};