青蛙跳台阶 python

青蛙跳台阶问题是一个经典的递归问题。假设青蛙可以一次跳上1级台阶或2级台阶，要跳上一个n级的台阶，共有多少种不同的跳法呢？

可以使用递归来解决这个问题，具体代码如下：

def frog_jump(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return frog_jump(n-1) + frog_jump(n-2)

这个函数会返回跳上n级台阶的不同跳法数。例如，调用`frog_jump(3)`将返回3，因为青蛙可以选择跳1级、1级、1级或者跳2级、1级两种方式。

但是，上述的递归解法存在重复计算的问题，效率较低。可以使用动态规划来优化求解过程，通过记录已经计算过的结果来避免重复计算，具体代码如下：

def frog_jump(n):
    if n <= 2:
        return n
    dp = [0] * (n+1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

这个函数也会返回跳上n级台阶的不同跳法数，并且通过动态规划的方法避免了重复计算，提高了效率。

希望能够帮助到你！如果有任何问题，请随时提问。

相关问题

青蛙跳台阶python

题目描述

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

示例1

输入

2

输出

2

示例2

输入

3

输出

3

解法1：递归（会超时）

class Solution:
def jumpFloor(self, number):
if number==1:
return 1
if number==2:
return 2
return self.jumpFloor(number-1)+self.jumpFloor(number-2)

解法2：循环

class Solution:
def jumpFloor(self, number):
if number==1:
return 1
if number==2:
return 2
a=1
b=2
for i in range(3,number+1):
c=a+b
a=b
b=c
return c

解法3：动态规划

class Solution:
def jumpFloor(self, number):
if number==1:
return 1
if number==2:
return 2
dp=[0]*(number+1)
dp[1]=1
dp[2]=2
for i in range(3,number+1):
dp[i]=dp[i-1]+dp[i-2]
return dp[number]

青蛙跳台阶python递归

以下是青蛙跳台阶的递归实现代码：

def jumpFloor(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return jumpFloor(n-1) + jumpFloor(n-2)

解释：

当只有一级台阶时，只有一种跳法；当有两级台阶时，有两种跳法（一次跳一级或一次跳两级），因此返回值为1和2；当有三级及以上的台阶时，可以考虑最后一次跳的次数：如果最后一次跳了一级台阶，那么在前面的n-1级台阶中有跳法f(n-1)种；如果最后一次跳了两级台阶，那么在前面的n-2级台阶中有跳法f(n-2)种。因此，跳n级的台阶的跳法数为f(n-1) + f(n-2)。