N阶楼梯上楼问题

题目描述：N阶楼梯上楼问题：一次可以走两阶或一阶，问有多少种上楼方式。
看到题目我的第一反应是求组合数，设走一阶的次数为p，走两阶的次数为q，最后只要满足p + 2 * q = N的结果就是解之一。在用组合数的计算公式(p + q)! / (p! * q!)，找到所有解，再把所有组合数的值相加就是总的方案数。代码如下：

public class Main {
    public static int count(int n) {
        int oneStep = 0, twoStep = 0, result = 0;
        for (oneStep = 0; oneStep <= n; oneStep++) {
            for (twoStep = 0; twoStep <= n / 2; twoStep++) {
                if (oneStep + twoStep * 2 == n) {
                    result += factorial(oneStep + twoStep) / factorial(oneStep) / factorial(twoStep);
                }
             }
        }
        
        return result;
    }
    
    public static int factorial(int n) {
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}

这是这样的代码一个用例没有通过，不清楚为什么。。IDE上运行是正常的，因此去搜索了一下问题的解法，找到一篇博客，思路如下：

走到第n阶时可能是从第n-1阶走一步到的，也可能是从n-2阶走两阶到的，设F(n)为走到n阶的种数，则F(n)=F(n-1)+F(n-2)。当n=1时，F(1)=1，n=2时，F(2)=2,这是一个动态规划问题。其实就是一个斐波那契数列。

因此我们的代码可以修改为

public int count(n) {
    if (n == 1 || n == 2) {
        return n;
    } else {
        return count(n-1) + count(n-2);
    }
}

牛客网的这一题要求稍微高点，不能用递归形式，其实也简单，但是有一点需要注意，斐波那契数列增长很快，当N为46时就已经超过了整型的范围，因此最后结果要用long来表示

public long count(n) {
    long one = 1, two = 2, result = 3;
    if (n == 1 || n == 2) {
        return n;
    } else {
        for (int i = 3; i <= n; i++) {
        result = one + two;
        one = two;
        two = result;
    }
  }
  return result;
}