Climbing Stairs（爬楼梯）

题目描述（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;
    }