题目描述

假设你正在爬楼梯。需要 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 阶

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法1

(暴力搜索) $O(玄学)$

使用爆搜，结果是T飞……

C++ 代码

class Solution {
public:
    int climbStairs(int n) {
        return dfs(n);
    }
    int dfs(int u)
    {
        if(u == 0) return 1;
        if(u == 1) return 1;
        if(u < 0) return 0;
        return dfs(u - 1) + dfs(u - 2);
    }
};

加一些小的优化也没啥大用……

class Solution {
public:
    int climbStairs(int n) {
        return dfs(n);
    }
    inline int dfs(int u)
    {
        if(u == 0) return 1;
        if(u == 1) return 1;
        if(u < 0) return 0;
        int res = dfs(u - 1) + dfs(u - 2);
        return res;
    }
};

算法2

(动态规划) $O(n)$

利用DP的思路，可得出状态转移方程为：
$f[i] = f[i - 1] + f[i - 2]$

时间复杂度 $O(n)$

代码极短,0ms!!!

C++ 代码

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