2020-08-10 08:20 武汉大学 后端
关注
跳台阶题目也是很经典的题目，前面做过了跳台阶的变体，这道题就变得简单了。
本质上，这就是“斐波那契数列”的应用，但考察我们对于问题的理解能力。青蛙跳上n级台阶，此时有三种情况：
- 当只有1级台阶时（n = 1），此时青蛙跳一次即可完成目标。
- 当有2级台阶时（n = 2），此时青蛙可以一次跳一级，也可以一次跳两级，也就是有2种跳法。
- 当青蛙跳n级台阶时（n >= 3），我们把n级台阶的跳法比作n的函数：f(n)。这时，我们考虑：如果青蛙第一步跳一级台阶，之后的跳法数目就是之后剩余n-1级台阶的跳法数目，即f(n-1)；另一种可能的情况就是青蛙第一步跳两级台阶，之后的跳法数目就是之后剩余的n-2级台阶的跳法数目；所以n级台阶的不同跳法的总数是f(n) = f(n-1) + f(n-2);
是不是就是斐波那契数列呀？哈哈，代码也很简单：
public int JumpFloor(int target) {
if (target == 1) {
return 1;
} else if (target == 2) {
return 2;
} else {
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
}
本质上，这就是“斐波那契数列”的应用，但考察我们对于问题的理解能力。青蛙跳上n级台阶，此时有三种情况：
- 当只有1级台阶时（n = 1），此时青蛙跳一次即可完成目标。
- 当有2级台阶时（n = 2），此时青蛙可以一次跳一级，也可以一次跳两级，也就是有2种跳法。
- 当青蛙跳n级台阶时（n >= 3），我们把n级台阶的跳法比作n的函数：f(n)。这时，我们考虑：如果青蛙第一步跳一级台阶，之后的跳法数目就是之后剩余n-1级台阶的跳法数目，即f(n-1)；另一种可能的情况就是青蛙第一步跳两级台阶，之后的跳法数目就是之后剩余的n-2级台阶的跳法数目；所以n级台阶的不同跳法的总数是f(n) = f(n-1) + f(n-2);
是不是就是斐波那契数列呀？哈哈，代码也很简单：
public int JumpFloor(int target) {
if (target == 1) {
return 1;
} else if (target == 2) {
return 2;
} else {
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
}
2020-08-10
在牛客打卡11天，今天学习：刷题 1 道/代码提交 1 次
全部评论
相关推荐
查看30道真题和解析