爬楼梯

---

• 原题链接：https://leetcode.cn/problems/climbing-stairs/

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

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

1.递推与递归

==思路==：简单的递推问题（斐波那契数列）

• 到达第一阶梯的方法数为1
• 到达第二阶梯的方法数为1
• 到达第三阶梯的方法数为 第一阶梯的方法数 + 第二阶梯的方法数
• ……
• 到达第n阶梯的方法数为 第 n - 1 阶梯的方法数 + 第 n - 2 阶梯的方法数
• ans[i] = ans[i - 1] + ans[i - 2];

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int ans[2] = {1, 2};
        int a = 0, b = 1;
        for (int i = 3; i <= n; ++i) {
            ans[a] += ans[b];
            swap(a, b);
        }
        return ans[b];
    }
};