青蛙跳台阶问题
2023-02-25 18:17:39 时间
文字表述
首先,当只有一级台阶时,毫无疑问,只有一种跳法
其次,当有两级台阶时,就是两种跳法
那么,三级台阶时,应该两种情况
1、若青蛙先跳一级台阶,接下来就有两种跳法,要么一级一级地跳,要么直接就跳上两级
2.若青蛙先跳两级台阶,接下来只能在再跳一级台阶
所以当有三级台阶时,一共有3种跳法
那么,一共有4级台阶时,一共有多少种跳法呢?
我们不妨列举一下
1.青蛙先跳一级台阶,接下来他就会还有3级台阶要去跳,而这3级台阶不就是上面3级台阶的重复吗!所以此时一共有3种跳法
2.青蛙先跳2级台阶,接下来他还有2级台阶要跳,此处也可以使用之前得出的2级台阶的结果,所以此时一共有2种跳法
所以当青蛙要跳4级台阶时,其实就是跳3级台阶的跳法加上跳2级台阶的跳法
总结:事实上,跳n级台阶的跳法就是跳n-1级台阶的跳法加上n跳-2级台阶的跳法,而这就可以使用递归的方法来解决
图片表述
跳一级就只有一种跳法
跳两级有2种跳法也是非常好理解的
当有3级台阶时,可能会稍微复杂一点
所以当有3级台阶时,一共有3种方法(其实就是有1级台阶和有两级台阶的跳法之和)
当有4级台阶时,其实也就是3级台阶和2级台阶的跳法之和
所以,要求有n级台阶时的跳法,其实就是n-1级台阶与n-2级台阶的跳法之和
代码如下:
public class Solution {
public int jumpFloor(int target) {
if(target==1){
return 1;
}else if(target==2){
return 2;
}else {
return jumpFloor(target-1)+jumpFloor(target-2);
}
}
}
青蛙跳台阶是一个十分经典的问题,要想解决这道题,就必须要了解递归的思想,掌握递归的核心:大事化小 但是,递归的效率又不是很理想,所以我们有必要进行代码的优化 所以我们可以模仿求斐波那契数字一样,使用循环来进行优化
public class Solution {
if (n == 1 || n == 2) {
return n;
} else {
int a = 1;
int b = 2;
int c = 0;
for (int i = 3; i <=n; i++) {
c = a + b;
a = b;
b = c;
}
return c;
}
}
这样子循环的效率就会高于递归的写法
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023