面试爬楼梯算法，每次可以跨一阶或者两阶，每次可以退后一步。求大神提供思路

前面有n节楼梯，每次可以跨一阶或者两阶，每次可以退后一步。求大神提供思路

• 你的题目没有写完整吧。不知道你最终要干什么
• 是不是这个下面题目？
• http://blog.sina.com.cn/s/blog_63627b0d0100lcmi.html

本质上和汉诺塔差不多，用堆栈解决

每次可以后退一步是在跨1或2步之后还是同时？

#include
#define N 1000005
using namespace std;
int num[N]; //num[i]=j表示上i阶楼梯，有j种方法。

int main() {
int n;
num[1] = 1;
num[2] = 2;
for(int i = 3; i < N; i++){ //为防止运行超时，每计算一个结果，就保存到数组中，用空间换取时间。
num[i] = num[i - 1] + num[i - 2];
if(num[i] >= 1000000007)
num[i] = num[i] % 1000000007;
}
while(scanf("%d",&n) != EOF){
printf("%d\n",num[n]);
}
return 0;
}
输入样例：
1
2
3
样例输出
1
2
3

public static int getResult2(int n) {
    int cache[][] = new int[n+1][2];
    return getResult(n,cache)[0] + getResult(n,cache)[1];
}
public static int[] getResult(int n, int cache [][]) {
    int result[] = {0,0};
    // 1
    if(n == 1) {
        result[0] = 1;
        result[1] = 0;
        return result;
    }
    if(n == 2) {
        result[0] = 1;
        result[1] = 1;
        return result;
    }
    if(n == 3) {
        result[0] = 2;
        result[1] = 1;
        return result;
    }

    if(cache[n][0] != 0 || cache[n][1] != 0) {
        return cache[n];
    }
    // 2
    int preResult2[] = getResult(n - 2,cache);
    int preResult1[] = getResult(n - 1,cache);
    result[0] = preResult2[0] + preResult2[1] + preResult1[1];
    result[1] = preResult2[0];
    cache[n][0] = result[0];
    cache[n][1] = result[1];



    return result;
}