牛客网剑指Offer 第8、9题：跳台阶 python

第8题

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）

思路

开始想的是函数的递归调用，因为每次有两种情况跳一步或两步，所以n级台阶的跳法应该等于n-1级台阶的跳法加n-2级台阶的跳法，见代码段1。
运行发现超时，然后想到这就是斐波那契数列的变形，函数之间的嵌套调用非常麻烦，所以改成了代码段2的形式，通过测试。

代码1

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        def oneStep(n):
            if n == 1:
                return 1
            elif n == 2:
                return 2
            else:
                return oneStep(n-1) + oneStep(n-2)
        if number == 0:
            return 0
        return oneStep(number)

代码2

   # -*- coding:utf-8 -*-
        class Solution:
            def jumpFloor(self, number):
                # write code here
                s = 0
                s1 = 1
                s2 = 2
                if number <= 2:
                    return number
                for i in range(number-2):
                    s = s1
                    s1 = s2
                    s2 = s+s1
                return s2

第9题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

思路

还是递归，第n级台阶的跳法等于前面所有台阶跳法的累加加上1（一步到位）。最后发现结果等于2^（n-1），-_-||

递归代码

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number <=2:
            return number
        l = [1 for i in range(number)]
        for i in range(1,number):
            l[i] = sum(l[0:i])+1
        return l[-1]

最后

以上就是优雅茉莉为你收集整理的牛客网剑指Offer 第8、9题：跳台阶 python的全部内容，希望文章能够帮你解决牛客网剑指Offer 第8、9题：跳台阶 python所遇到的程序开发问题。

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