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