关注
一、确定初始状态
当井高为 1 米时,青蛙只有一种跳法,即一天直接跳 1 米到达井口,所以 f(1)=1。
当井高为 2 米时,青蛙可以一天跳 2 米直接出来,或者分两天每天跳 1 米,这两种情况构成了跳上 2 米高井的所有方法,所以 f(2)=2。
二、推导递推关系
对于井高 n>2 的情况,考虑青蛙最后一步的跳法。
如果最后一步跳 1 米,那么前面 n - 1 米的跳法数量就是 f(n - 1),因为最后一步确定了,只需要考虑前面 n - 1 米的跳法。
如果最后一步跳 2 米,那么前面 n - 2 米的跳法数量就是 f(n - 2),同理最后一步确定为跳 2 米,只需要考虑前面 n - 2 米的跳法。
所以总的跳法数量 f(n)就是前面两种情况的和,即 f(n)=f(n - 1)+f(n - 2)。
三、计算 f(100)
依次计算 f(3)=f(2)+f(1)=2 + 1 = 3。
f(4)=f(3)+f(2)=3 + 2 = 5。
以此类推,逐步计算下去,直到计算出 f(100),就能得到青蛙跳出 100 米井的方法数。
查看原帖
2 评论
相关推荐
点赞 评论 收藏
分享
04-16 03:09
中国地质大学(武汉) Java 点赞 评论 收藏
分享
牛客热帖
更多
- 1... 本科四段大厂实习,暑期五个offer,我的暑期结束了,秋招前集邮atmd、上海四毒3.2W
- 2... 一文讲清新手到底要不要写《苍穹外卖》和《黑马点评》?1.0W
- 3... 黑马点评大总结1.0W
- 4... 实习/试用期转正,如何写好答辩文档?4407
- 5... 拼多多PDD-5.5服务端研发实习生二面面经4029
- 6... 节后上班第一天,我的精神状态be like……3663
- 7... Java后端5月还会有机会吗3351
- 8... 只有真正上战场了,才知道自己多菜!3248
- 9... 拼多多17-20号信息确认3198
- 10... 历时两周,看我如何速通腾讯!2636
正在热议
更多
# 你上一次加班是什么时候? #
50385次浏览 351人参与
# 学历or实习经历,哪个更重要 #
96805次浏览 694人参与
# 深信服求职进展汇总 #
178746次浏览 1663人参与
# 租房找室友 #
15186次浏览 101人参与
# 秋招最大的收获是什么? #
25059次浏览 275人参与
# 秋招签约后的心态变化 #
74720次浏览 791人参与
# 如何排解工作中的焦虑 #
150542次浏览 1752人参与
# 大疆求职进展汇总 #
479579次浏览 3195人参与
# 实习要如何选择和准备? #
58427次浏览 957人参与
# 秋招想进国企该如何准备 #
51006次浏览 350人参与
# 牛友打假中心 #
83186次浏览 2633人参与
# 如果可以,你希望哪个公司来捞你 #
71613次浏览 311人参与
# 生化医药面经大本营 #
100516次浏览 466人参与
# 多益网络求职进展汇总 #
22403次浏览 126人参与
# 摸鱼被leader发现了怎么办 #
50628次浏览 323人参与
# 如果重来一次你还会读研吗 #
167697次浏览 1754人参与
# 找工作,行业重要还是岗位重要? #
28886次浏览 496人参与
# 实习工作,你找得还顺利吗? #
402967次浏览 5576人参与
# 产品每日一题 #
39528次浏览 551人参与
# 荣耀求职进展汇总 #
845855次浏览 4762人参与