题目描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解题思路
牛客上评论比较多的一个解法：
f(1) = 1
f(2) = f(2-1)+f(2-2) //f(2-2)表示2阶时一次跳的次数
f(3)=f(3-1)+f(3-2)+f(3-3) //在第二阶时跳1阶，在第一阶时跳2阶，在在开始时跳3阶总和
...
f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(n-(n-1))+f(n-n)
说明：
- 这里的f(n) 代表的是n个台阶有一次1,2,...n阶的 跳法数。
- n = 1时，只有1种跳法，f(1) = 1
- n = 2时，会有两种跳的方式，一次1阶或者2阶，既有f(2) = f(2-1) + f(2-2)
- n = 3时，会有三种跳的方式，1阶、2阶、3阶，那么就是第一次跳出1阶后面剩下：f(3-1);第一次跳出2阶，剩下f(3-2)；第一次3阶，那么剩下f(3-3) ，因此结论是f(3) = f(3-1)+f(3-2)+f(3-3)
- n = n时，会有n中跳的方式，1阶、2阶...n阶，得出结论： f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n)，即： f(0) + f(1) + f(2) + f(3) + ... + f(n-1)
- 由以上已经是一种结论，但是为了简单，我们可以继续简化：
f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)
可以得出： f(n) = 2*f(n-1)
参考代码
Java
public class Solution {
public int JumpFloorII(int target) {
if (target <= 0)
return 0;
int fn1 = 1, fn2 = 1;
for (int i = 2; i <= target; i++) {
fn2 = fn1 * 2;
fn1 = fn2;
}
return fn2;
}
}
Python
class Solution:
def jumpFloorII(self, number):
# write code here
if number<=0:return 0
fn1,fn2 = 1,1
for i in range(2, number + 1):
fn2 = fn1*2
fn1 = fn2;
return fn2
个人订阅号
image