动态规划青蛙跳台阶python代码

下面是青蛙跳台阶的动态规划 Python 代码示例：

def jump_floor(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for i in range(3, n+1):
        c = a + b
        a, b = b, c
    return c

在这个代码中，我们使用了动态规划来解决青蛙跳台阶的问题。我们用变量a、b和c来表示f(i-2)、f(i-1)和f(i)。在每次循环中，我们将a和b分别更新为上一个状态的值，然后用它们来计算c的值。最后我们返回c作为结果。

这个算法的时间复杂度是O(n)，空间复杂度是O(1)，因为我们只使用了常数个变量来存储中间结果。

相关问题

青蛙跳台阶 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递归

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

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)。