一、题目描述

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 45

二、解题思路

1. 如果楼梯只有 1 阶或 2 阶，那么方法数就等于楼梯的阶数，因为只有一种方法可以到达第一阶（爬一阶），有两种方法可以到达第二阶（爬两阶或先爬一阶再爬一阶）。

2. 对于超过 2 阶的楼梯，我们使用一个循环来计算每一阶的方法数。我们初始化两个变量 a 和 b 分别为 1 和 2，它们代表到达第一阶和第二阶的方法数。

3. 从第三阶开始，我们使用一个循环来计算每一阶的方法数。对于每一阶 i，我们计算到达它的方法数 temp，这个方法数是到达前两阶的方法数之和（a + b）。

4. 然后，我们将 a 更新为 b，将 b 更新为 temp。这样，在下一轮循环中，a 将代表到达前一级的方法数，而 b 将代表到达当前级的方法数。

5. 当循环结束时，b 将包含到达第 n 阶的方法数，我们将其返回作为结果。

三、具体代码

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        
        int a = 1, b = 2, temp;
        for (int i = 3; i <= n; i++) {
            temp = a + b;
            a = b;
            b = temp;
        }
        
        return b;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• O(n) 这是因为代码中有一个从 3 到 n 的循环，循环的次数与 n 的值成正比。
• 在这个循环中，每次迭代只进行了常数时间的操作（即计算两个数的和，并更新这两个数）。
• 因此，总的时间复杂度是 O(n)。

2. 空间复杂度

• O(1) 代码中只使用了几个固定数量的变量（a、b 和 temp）来存储中间结果，而不是使用与 n 成正比的额外空间。
• 因此，不管输入的 n 有多大，所需的额外空间都保持不变，即常数空间。
• 所以，空间复杂度是 O(1)。

五、总结知识点

1. 基础编程概念：

• 变量的声明和初始化：int a = 1, b = 2, temp; 声明了三个整型变量 a、b 和 temp，并初始化 a 和 b。
• 循环结构：for 循环用于重复执行一组语句，直到指定的条件不再满足。在这个代码中，循环从 3 运行到 n。

2. 递推关系：

• 斐波那契数列：代码使用了一个递推关系来计算斐波那契数列中的第 n 个数，即 F(n) = F(n-1) + F(n-2)，其中 F(1) = 1 和 F(2) = 2。

3. 动态规划：

• 动态规划是一种算法设计技术，它将复杂问题分解成更小的子问题，并存储这些子问题的解，以避免重复计算。在这个代码中，a 和 b 变量分别存储了到达前两个楼梯阶的方法数，而 temp 存储了到达当前楼梯阶的方法数。

4. 算法优化：

• 空间优化：代码通过只存储前两个斐波那契数，而不是使用数组来存储所有的斐波那契数，从而将空间复杂度从 O(n) 降低到 O(1)。

5. 边界条件处理：

• 代码首先检查 n 的边界条件，如果 n 小于等于 2，则直接返回 n，这是因为斐波那契数列的前两个数是固定的。

6. 迭代与递归：

• 虽然斐波那契数列可以通过递归方式轻松实现，但递归解决方案通常效率低下，因为它会进行大量的重复计算。这段代码使用迭代方法来计算斐波那契数列，这是一种更高效的实现方式。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。