🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

一、题目描述
假设你正在爬楼梯。需要爬 n 阶才能到达楼顶。每次可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

二、测试样例
输入： 3

输出： 3

说明： 有三种方法可以爬到楼顶。

（1） 1 阶 + 1 阶 + 1 阶，1 阶 1 阶的爬；

（2） 1 阶 + 2 阶，先爬 1 阶，然后，爬 2 阶；

（3） 2 阶 + 1 阶，先爬 2 阶，然后，爬 1 阶；

所以，爬 3 阶的楼梯总共有三种方法。

三、算法思路
这题非常经典，可以使用动态规划的思想，假设 dp[i] 为爬 i 阶的楼梯总共的方法，那么，就有如下的转移方程：

dp[i] = dp[i-1] + dp[i-2] (i > 1)

即：爬到第 i 个阶的方法数等于从第 dp[i-1] 和 dp[i-2] 的和，因为只能爬 1 阶或 2 阶。

因为本题不需要保存爬每一阶的方法数，故可以将上述公式改成如下方式：

ans = first + second

first 为 dp[i-1]，second 为 dp[i-2]，不断更新 first 和 second 的值。

四、代码实现

class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2) return n; // 小于 2 直接返回对应值
        int ans = 0;
        int first = 1, second = 2;
        for(int i = 3; i <= n; ++i) { // 大于 2 的情况
            ans = first + second;   // 求 ans
            first = second;  // 更新 first
            second = ans;    // 更新 second
        }
        return ans;
    }
};

五、复杂度分析
时间复杂度：O(n)，很明显，一层 for 循环，时间复杂度为 O(n)；

空间复杂度：O(1)，仅适用了 3 个临时变量，可以忽略，故空间复杂度为 O(1)；

六、题目链接
https://leetcode-cn.com/problems/climbing-stairs/

CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

欢迎小伙伴们点赞👍、收藏⭐、留言💬