我是靠谱客的博主 糊涂刺猬,这篇文章主要介绍【算法入门08】青蛙跳台阶,现在分享给大家,希望可以做个参考。

核心考点:场景转化模型,模型提取解法,简单dp,fib

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求青蛙跳上一个n级的台阶共有多少种跳法(先后次序不同算不同的结果)。
在这里插入图片描述
解析:

对于这道题目,我们若是使用正向思维去思考,那这道题会变得非常困难,这时我们可以考虑使用逆向思维。

既然青蛙最终会到达第n级台阶,那青蛙必定是从第n-1级台阶或是第n-2级台阶跳到第n级台阶的。
在这里插入图片描述
也就是说青蛙跳到第n级台阶的总跳法数,等于青蛙跳到第n-1级台阶的总跳法数和青蛙跳到第n-2级台阶的总跳法数之和,即 f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n1)+f(n2)

当然,我们不能让这个公式一直往前推,总得给它一个尽头,我们很容易得到青蛙跳到第0级台阶的总跳法数,和青蛙跳到第1级台阶的总跳法数:

  • f ( 0 ) = 1 f(0)=1 f(0)=1,青蛙跳到第0级台阶的跳法只有一种,那就是不跳。
  • f ( 1 ) = 1 f(1)=1 f(1)=1,青蛙跳到第1级台阶的跳法也只有一种,那就是从第0级台阶直接跳到第1级台阶。

这时代码也就出来了,我们可以使用递归来解决该问题:

//递归
class Solution {
public:
	int jumpFloor(int number) {
		if (number == 0 || number == 1) //f(0)=1, f(1)=1
			return 1;
		return jumpFloor(number - 1) + jumpFloor(number - 2); //f(n)=f(n-1)+f(n-2)
	}
};

再仔细看看这段代码,这其实就是求第n个斐波那契数的代码,只不过数的下标变成了从0开始而已。

因此,青蛙跳台阶的解法和求第n个斐波那契数的解法相同,使用递归会产生大量重复计算,最优解法还是使用动态规划。

//动规
class Solution {
public:
	int jumpFloor(int number) {
		if (number == 0 || number == 1) //f(0)=1, f(1)=1
			return 1;
		int first = 1; //f(0)=1
		int second = 1; //f(1)=1
		int third = 0;
		while (number > 1) //进行number-1次计算
		{
			//f(n)=f(n-1)+f(n-2)
			third = first + second;
			first = second;
			second = third;
			number--;
		}
		return third;
	}
};

最后

以上就是糊涂刺猬最近收集整理的关于【算法入门08】青蛙跳台阶的全部内容,更多相关【算法入门08】青蛙跳台阶内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(48)

评论列表共有 0 条评论

立即
投稿
返回
顶部