剑指Offer:(变态)跳台阶

跳台阶

题目

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

分析

首先我们先来分析一种情况:
如果只有一个台阶,显然只有一种方法。
如果有两个台阶,要么分两步(一次跳一个台阶),要么一次跳两个台阶。
现在我们假设n个台阶一共有f(n)种走法。
青蛙最后一步要么跳一个台阶,要么跳两个台阶
当最后一步跳一个台阶时,那么它之前就有n-1个台阶,即有f(n-1)种走法
当最后一步跳两个台阶时,那么它之前就有n-2个台阶,即有f(n-2)种走法
所以n个台阶的走法就等于前两种走法的和,即f(n)=f(n-1)+f(n-2)。

看到这个公式,有没有感到很熟悉呢? ✔跟上两篇博客剑指Offer:斐波纳契数列剑指Offer:矩形覆盖所写的一样都是斐波纳契。
那么代码实现也就迎刃而解了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int JumpFloor(int target) {
if(target < 3)
return target;
int a = 1;
int b = 2;
int c = 0;
for (int i = 3; i <= target; i ++){
c = a+b;
a = b;
b = c;
}
return c;
}
}

变态跳台阶

题目

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

分析

显然这是根据上面那道跳台阶题目的延伸,所以我们可以在上道题的基础上来分析。

假定第一次跳的是一阶,那么剩下的是n-1个台阶,跳法是f(n-1);假定第一次跳的是2阶,那么剩下的是n-2个台阶,跳法是f(n-2);假定第一次跳的是3阶,那么剩下的是n-3个台阶,跳法是f(n-3)……假定第一次跳的是n-1阶,那么剩下的是1个台阶,跳法是f(1); 假定第一次跳的是n阶,那么剩下的是0个台阶,跳法是1种。

所以,总跳法为: f(n) = 1+f(n-1) + f(n-2)+….+f(1) (第一个1是跳n阶只有一种方法)

根据以上分析可以得出有一阶的时候 f(1) = 1 ;有两阶的时候可以有 f(2) = 1+f(1)=2;有三阶的时候可以有 f(3) = 1+f(2)+f(1)=4…依次内推,有n阶时f(n)=2^(n-1)

这里我们还可以通过位运算来加快运算速度。

1
2
3
4
5
public class Solution {
public int JumpFloorII(int target) {
return 1<<--target;
}
}

有收获再赞赏哦🤭
------ 本文结束感谢您的阅读-------------
0%