如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习校招总结offer选择也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

# 70. 爬楼梯

力扣原题链接(点我直达) (opens new window)

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

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

**注意:**给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶
1
2
3
4
5

示例 2:

输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶
1
2
3
4
5
6

# 第一版,其实很巧妙的题目

执行用时 :4 ms, 在所有 cpp 提交中击败了67.85%的用户

内存消耗 :8.5 MB, 在所有 cpp 提交中击败了35.19%的用户

	if (n == 0) return 0;
	if (n == 1) return 1;
	vector<int> res(n+1, 0);
	res[1] = 1;
	res[2] = 2;
	for (int i = 3; i <= n; ++i) {
		res[i] = res[i - 1] + res[i - 2];
	}
	return res[n];
1
2
3
4
5
6
7
8
9

# 第二版,稍微改进一下

执行用时 :4 ms, 在所有 cpp 提交中击败了67.85%的用户

内存消耗 :8.2 MB, 在所有 cpp 提交中击败了81.26%的用户

    int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14