题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
思路
如果青蛙当前在第n级台阶上,那它上一步是在哪里呢?显然,由于它可以跳1级台阶或者2级台阶,所以它上一步必定在第n-1,或者第n-2级台阶,也就是说它跳上n级台阶的跳法数是跳上n-1和跳上n-2级台阶的跳法数之和。
设跳上 级台阶有
种跳法,则它跳上n级的台阶有
种跳法。然后,我们又思考初始(
)的情况,跳上1级台阶只有1种跳法,跳上2级台阶有2种跳法,最终我们得到如下的递推式:
1、递推版实现
时间复杂度 O(2^n)O(2n)。
public class Solution {
public int JumpFloor(int target) {
if(target <= 2) {
return target;
}
return JumpFloor(target - 1) + JumpFloor(target - 2);
}
}
2、自底向上型循环求解,时间复杂度为 O(n)O(n)。
public class Solution {
public int JumpFloor(int target) {
if(target <= 2){
return target;
}
int pre2 = 1, pre1 = 2;
for (int i = 3; i <= target; i++){
int cur = pre2 + pre1;
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
}