给出一个楼梯阶数，每次只能走一阶或两阶，求所有的走法
比较笨的方法
类似鸡兔同笼问题，设置oneStepCount和twoStepCount两个变量，然后利用排列累加，但是需要注意求阶乘的时候溢出的问题
斐波那契数列
当n=1,2,3,4,5,6,7时，可以得到结果1, 2, 3, 5, 8, 13, 21，显然这是一个斐波那契数列(但我竟然没看出来。。)，用递归或非递归方法都可以解
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
int x = 3, result = 0, a = 1, b = 2;
while (x <= n) {
result = a + b;
a = b;
b = result;
x++;
}
return result;
}
一个另类的解法
观察这个结果，可以发现另一种规律，假设result[n]存放结果，下标从1开始
n = 4时，结果可以写成result[4 - 1] * 2 - result[4 - 3]，即3 * 2 - 1
n = 5时，结果可以写成result[5 - 1] * 2 - result[5 - 3]，即5 * 2 - 2
依次类推，大胆的猜这个数列的递推式为result[n] = result[n - 1] * 2 - result[n - 3]
但是需要注意处理n = 1, 2, 3时的情况
public int climbStairs(int n) {
int[] temp = new int[n];
if (n == 1) {
return 1;
}
if (n == 2) {
return 2;
}
if (n == 3) {
return 3;
}
temp[0] = 1; temp[1] = 2; temp[2] = 3;
int x = 3;
while (x < n) {
temp[x] = temp[x-1] * 2 - temp[x - 3];
x++;
}
return temp[n-1];
}
