70.爬楼梯

题目描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例：

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

解题方法：简单一看，此题便是典型的斐波那契数列，即当 n >= 3 时，f(n) = f(n - 1) + f(n - 2)。那么，此题就有两种方法，迭代和递归。需要注意的是在 LeetCode 中使用递归的时候会超时。代码如下：

public class ClimbStairs {

    // 迭代
    public static int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int temp1 = 1;
        int temp2 = 2;
        for (int i = 3; i <= n; i++) {
            int result = temp1 + temp2;
            temp1 = temp2;
            temp2 = result;
        }
        return temp2;
    }

    // 递归
    public static int climbStairs2(int n) {
        if (n == 1 || n == 2) {
            return n;
        } else {
            return climbStairs2(n - 1) + climbStairs2(n - 2);
        }
    }

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        int result = climbStairs(6);
        System.out.println("result = " + result);
        long endTime = System.currentTimeMillis();
        System.out.println("程序运行时间：" + (endTime - startTime) + "ms");
    }

}