题目描述（Easy）

假设一个楼梯有n梯，每次只能爬1梯或2梯，求出有多少种爬的方式。

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

样例

示例 1：

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

示例 2：

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

题目链接

Climbing Stairs（爬楼梯）

方法思路

第一直觉

递归：f(n) = f(n - 1) + f(n - 2)。但太慢，因为会重复计算很多次f(k)(k <= n)。

变量记录方式

1、考虑preNumDistinctWays记录前一梯的方法数；

2、令当前方法数distinctWays，加上前一梯preNumDistinctWays方法数，就是下一梯求的方法数；distinctWays+= preNumDistinctWays。

通项公式

另外，菲波拉契数列也有通项公式：

核心代码

public int climbStairs(int n) { // 前一梯的方法数 int preNumDistinctWays = 0; // 求的总方法数 int distinctWays = 1; for (int i = 1; i <= n; i++) { // 未加之前方法数临时变量 int temp = distinctWays; // 当前方法数 += 前一梯方法数 distinctWays += preNumDistinctWays; // 将临时变量赋值给前一梯方法数变量 preNumDistinctWays = temp; } return distinctWays; }