假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

Solution

参考**@覃超**的思路

• 递归解法，时间复杂度为 O(2^n^)

# @lc code=start
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <=2:
            return n
        return self.climbStairs(n-1)+self.climbStairs(n-2)
# @lc code=end

• 打印爬楼梯步骤

class Solution:
    def climbStairs(self, n: int) -> int:
        
        self._dfs(n, [])

    def _dfs(self, n, res):
        if n>=0:
            if n == 0:
                print(res)

            self._dfs(n-1, res+[1])
            self._dfs(n-2, res+[2])

n = 5
s = Solution()
s.climbStairs(n)

动态规划

• 记忆化搜索，自顶向下

// @lc code=start
class Solution {
private:
    vector<int> memo;

    int dp(int n){
        if(n==0 || n==1)
            return 1;
        
        if(memo[n]==-1)
            memo[n] = dp(n-1)+dp(n-2);
        return memo[n];
    }

public:
    int climbStairs(int n) {
        memo = vector<int>(n+1, -1);
        int res = dp(n);
        return res;
    }
};
// @lc code=end

• 自底向上

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