青蛙跳（递归）
发布于2019-08-07 12:49 阅读(820) 评论(0) 点赞(4) 收藏(4)
题目描述1
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
分析：
对于第n个台阶来说，只能从n-1或者n-2的台阶跳上来，所以F(n) = F(n-1) + F(n-2)，看到这儿就熟悉了吧，这不就是斐波拉契数列嘛，对的，就是。只是换了说法而已。
但是尝试用递归实现时却超时，如下：
只能换种方法：
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
res = [1,2]
while len(res) <= number:
res.append(res[-1]+res[-2])
return res[number-1]- 1
- 2
- 3
- 4
- 5
- 6
- 7
题目描述2
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
分析：
对于第n个台阶来说，可以从n-1，n-2，…0（0代表起点）上跳上来，所以就是对之前所有台阶求和。（一定不要忘记可以从起点直接到终点）
代码如下：
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
res = [1,2]
while len(res) <= number:
res.append(sum(res)+1)
return res[number-1]- 1
- 2
- 3
- 4
- 5
- 6
- 7
补充：
对于此问题。看了大佬的思路，更是666，如下：
题目描述3
我们可以用2 x 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 x 1的小矩形
无重叠地覆盖一个2 x n的大矩形，总共有多少种方法？
分析：
F(n) = F(n-1) + F(n-2)，因此本质上还是斐波拉契数列。
代码如下：
所属网站分类: 技术文章 > 博客
作者：你太美丽
链接：https://www.pythonheidong.com/blog/article/11001/008a6b118689cce94819/
来源：python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力