青蛙跳台阶和变态跳台阶

Quirita ·

更新时间:2024-09-21

· 739 次阅读

青蛙跳台阶和变态跳台阶（python、剑指Offer） 一、题目描述

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

二、青蛙跳台阶算法

类似于Fibonacci数列的算法问题
台阶数为number或n，跳法数为ret，f(n)代表跳到第n阶台阶的跳法数

算法流程分析

在这里插入图片描述
由于青蛙每次只能跳一个台阶或者两个台阶，故
f(n) = f(n-1) + f(n-2)
注：青蛙跳到每一个台阶只有两种可能
1.从第n-1阶台阶一次跳1阶，到达第n阶
2.从第n-2阶台阶一次跳2阶，到达地n阶

代码示例

class Solution:
    def jumpFloor(self, number):
        # write code here
        if number < 1:
            return 0
        if number == 1:
            return 1
        if number == 2:
            return 2
        ret = 0
        a = 1
        b = 2
        for i in range(3,number + 1):
            ret = a + b 
            a = b 
            b = ret 
        return ret 
		#此代码缺少输出输出

注：range()函数是一个左闭右开的区间，注意区分Fibonacci数列算法与青蛙跳台阶算法中range()函数的循环始终

三、变态跳台阶算法（贪心算法）

台阶数为number或n，跳法数为ret，f(n)代表跳到第n阶台阶的跳法数

方法一：找规律

number = 0 时，ret = 0
number = 1 时，ret = 1
number = 2 时，ret = 2
number = 3 时，ret = 4
number = 4 时，ret = 8
…
number = n 时，ret = 2^(n-1)

代码示例

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        return 2 ** (number - 1)
        #此代码缺少输入输出

方法二：贪心算法 算法流程解析

在这里插入图片描述
从第n个台阶开始倒推：
1：可能是从第n-1个台阶跳到第n个台阶（跳了1阶）
2：可能是从第n-2个台阶跳到第n个台阶（跳了2阶）
…
n-1：可能是从第1个台阶跳到第n个台阶（跳了n-1阶）

推得 f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(1)
f(n-1) = f(n-2) + f(n-3) + f(n-4) + … +f(1)
故 f(n) = f(n-1) + f(n-1)
=2 * f(n-1)

代码示例

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number == 0:
            return 0
        if number == 1:
            return 1
        ret = 1
        a = 1
        for i in range(2,number + 1):
            ret = 2 *a 
            a = ret
        return ret 
		#此代码缺少输出输出

作者：Coisini108

青蛙

1024 个赞