跳台阶（递归循环）

68 阅读 0 评论 45 点赞

我是靠谱客的博主儒雅茉莉，这篇文章主要介绍跳台阶（递归循环），现在分享给大家，希望可以做个参考。

题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析：

*当有n个台阶时，假设有f(n)种走法。

*青蛙最后一步跨1个台阶或者跨2个台阶。

*当最后一步跨1个台阶时即之前有n-1个台阶，n-1个台阶有f(n-1)种走法；当最后一步跨2个台阶时即之前有n-2个台阶，n-2个台阶有f(n-2 )种走法。

*n个台阶的走法等于前两种情况的走法之和，即f(n)=f(n-1)+f(n-2)。

*斐波那契数列

思路一：递推

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int JumpFloor(int target) {
        if (target <= 1) return 1;
        int [] sum = new int[target + 1];

        sum[0] = 1;
        sum[1] = 1;
        sum[2] = 2;
        if (target >= 3)
        {
            for (int i = 3; i <= target; i++)
                sum[i] = sum[i -1] + sum[i - 2];
        }
        return sum[target];
    }
}

思路二：递归

复制代码

1
2
3
4
5
6
7
8
public class Solution {
    public int JumpFloor(int target) {
        if (target <= 1)
            return 1;
        else
            return JumpFloor(target - 1) + JumpFloor(target - 2);
    }
}