【剑指offer】10-II.青蛙跳台阶问题Python3

Python3

先简单列举一些台阶级数，看看有无数学规律：
  当台阶为0级时，有1种跳法；
  当台阶为1级时，有1种跳法；
  当台阶为2级时，有2种跳法；
  当台阶为3级时，有3种跳法；
  …
  当台阶为7级时，有21种跳法；
  …
  当台阶为n级时，有?种跳法。
好像看不出有什么规律。
换个思路：
  我们假设台阶的级数为$n$，青蛙有$F(n)$种跳法。无论如何，青蛙的最后一跳，要么是跳1级台阶，要么是跳2级台阶。可以知道：
  1.当最后一跳跳了1级台阶，那么之前跳了$n-1$级台阶，这$n-1$级台阶青蛙有$F(n-1)$种跳法；
  2.当最后一跳跳了2级台阶，那么之前跳了$n-2$级台阶，这$n-2$级台阶青蛙有$F(n-2)$种跳法。
  因此有$F(n)=F(n-1)+F(n-2)$，这就是斐波那契数列的表达式了。
参考【剑指offer】10-I.斐波那契数列的代码，可以写出本题的代码，如下：

class Solution:
	def numWays(self, n: int) -> int:
		a, b = 1, 1  # a,b分别表示当台阶数为0时和台阶数为1时青蛙跳法的种数
		for _ in range(n):
			sum = a + b
			a, b = b, sum
		return a % 1000000007

提交之后，答案正确。
时间复杂度分析
采用for循环遍历$n$次，因此时间复杂度是$O(n)$。

最后

以上就是贪玩柜子为你收集整理的【剑指offer】10-II.青蛙跳台阶问题Python3的全部内容，希望文章能够帮你解决【剑指offer】10-II.青蛙跳台阶问题Python3所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。