一、leetcode算法

1、爬楼梯

1.1、题目

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

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

示例 1：

输入：n = 2

输出：2

解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶

2 阶

示例 2：

输入：n = 3

输出：3

解释：有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶

1 阶 + 2 阶

2 阶 + 1 阶

1.2、思路

思路一：本题是一道经典的算法题，爬楼梯的问题和我们的生活息息相关，我们几乎每天都需要爬楼梯，我们有时会一阶一阶的上，有时赶时间我们会两阶两阶的蹭蹭的上，有时候累了会两阶一阶交叉着上，那么固定的楼梯阶层数我们一共有几种上楼的方式呢？

我们拿到问题以后如果没有思路可以先找找规律，犹如我们数学中给你几个数或者几个图形让你找规律一样，这个时候我们从1阶楼梯开始找共有几种方式，我们发现，1阶楼梯有一种上楼方式，2阶楼梯有两种上楼方式，3阶楼梯有3种上楼方式，4阶楼梯有5中上楼方式，我们这里可以发现每x阶层的上楼方式等于x-1层和x-2层上楼方式的和，这个时候我们就可以根据这种规律来写代码了。

1.3、答案

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for(int i = 1; i <= n; i++){
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
}

复杂度分析

时间复杂度：循环执行 n 次，每次花费常数的时间代价，故渐进时间复杂度为 O(n)。

空间复杂度：这里只用了常数个变量作为辅助空间，故渐进空间复杂度为 O(1)。