Hello_xzy_Word 2020-03-29 20:06:04 260 收藏 1
分类专栏: 在线编程
版权
题目描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
我的解法
public int JumpFloor1(int target) {
if (target == 1) {
return 1;
} else {
int total = 0;
for (int i = 1; i < target; i++) {
total += JumpFloorII(target - i);
}
return total+1;
}
}
1
2
3
4
5
6
7
8
9
10
11
大佬的解法
① f(n) = f(n-1) + f(n-2) +f(n-3) + … + f(2) + f(1)
② f(n-1) = f(n-2) +f(n-3) + … + f(2) + f(1)
由①②得,f(n) = 2f(n-1);
public static int jumpFloor2(int target) {
if (target == 1) {
return 1;
} else {
return 2 * jumpFloor2(target - 1);
}
}
1
2
3
4
5
6
7
终极解法
f(n) = 2f(n-1) (n>=2)
f(n) = 1 (n=1)
递归方程求解:
f( n ) = 2f( n - 1 )
= 2*2f( (n-1) - 1 ) = 22f( n - 2 )
= 2*2*2f( (n-2) - 1 ) = 23f( n - 3 )
=2*2*2*2*…*2f( (n-*(n-3)) -1) = 2n-2f( n - (n-2) ) = 2n-2f( 2 )
=2*2*2*2*…*2f( (n-*(n-2)) -1) = 2n-1f( n - (n-1) ) = 2n-1f( 1 ) = 2n-1
public int JumpFloor3(int target) {
return (int) Math.pow(2, target - 1);
————————————————
版权声明:本文为CSDN博主「Hello_xzy_Word」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/qq_39514033/article/details/105184956