跳台阶问题【递归+非递归】

84 阅读 0 评论 56 点赞

我是靠谱客的博主听话豆芽，这篇文章主要介绍跳台阶问题【递归+非递归】，现在分享给大家，希望可以做个参考。

可以跳一阶台阶，也可以跳2阶，求跳n 阶的方法

递归：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
public int jumpfloor(int n){

        if (n==0){
            return 0;
        } else if (n==1){
            return 1;
        } else if(n==2){
            return 2;
        }else{
            return jumpfloor(n-2)+jumpfloor(n-1);
        }
    }

n代表还有多少没跳的

f(0)=0;
f(1)=1;
f(2)=f(2-1)+f(2-2);//当还剩下两阶时，紧接着还可以在跳一阶，两阶
f(3)=f(3-1)+f(3-2);

2.非递归，迭加

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//自底向上的动态规划
public long long solution(int number)
{
    //题目保证 number 最大为100
    static long long Counter[101] = {0};
    Counter[1] = 1;
    Counter[2] = 2;
    static int calculatedIndex = 2;
 
    if(number <= calculatedIndex)
        return Counter[number];
 
    //防止下标越界
    if(number > 100)
        number = 100;
 
    for(int i = calculatedIndex + 1; i <= number; i++)
    {
        Counter[i] = Counter[i - 1] + Counter[i - 2];
    }
    calculatedIndex = number;
    return Counter[number];
}