LeetCode：楼梯问题

问题

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

翻译

假设有一个n层的楼梯，每次你可以走1到2层。
有多少不同的方法可以走上去？

思路

第n层只可以从第n-1层走1层或者n-2层走2层到达。因此第n层的总方法数是第n-1层和n-2层之和。抽象后此问题成为了一个斐波那契数列问题。

代码

递归解法：

public static int climbStairs(long n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

非递归解法：

public static int climbStairs(long n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        int all = 0, past = 2, pastTwo = 1;
        int i = 3;
        do{
            all = past + pastTwo;
            pastTwo = past;
            past = all;
            i++;
        }while (i <= n);
        return all;
    }