小青蛙爬楼梯python

小青蛙爬楼梯的问题通常是一个经典的动态规划问题，可以用Python通过递归或循环的方式来解决。这里我们假设有一只青蛙从楼梯的底部开始，每次可以向上跳一级或两级。目标是找到青蛙能到达楼顶的所有可能跳跃路径。

这是一个典型的斐波那契数列应用场景，我们可以创建一个函数，例如`fib_ways(n)`，其中n代表楼层高度，返回青蛙达到顶层的路径数量。

def climb_stairs(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    else:
        # 使用动态规划的思想
        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 = 5  # 青蛙有5层楼可爬
ways = climb_stairs(n)
print(f"青蛙可以有 {ways} 种不同的爬法。")

相关问题

小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。 河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃 后使石头高度下降到 0 是允许的）。 小青蛙一共需要去学校上 x 天课, 所以它需要往返 2 x 次。当小青蛙具有一个跳跃能力 y时, 它能跳不超过 y的距离。 请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x次课。 输入格式 输入的第一行包含两个整数 n , x分别表示河的宽度和小青蛙需要去学校的天数。请注意 2 x才是实际过河的次数。 第二行包含 n − 1个非负整数 H 1 , H 2 , ⋯ , H n − 1 , 其中 H i >0，表示在河中与小青蛙的家相距 i 的地方有一块高度为 H i的石头,H i = 0表示这个位置没有石头。 输出格式 输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。 样例输入 5 1 1 0 1 0 样例输出 4

这是一道典型的二分答案问题。我们可以二分跳跃能力 y，然后验证是否能够通过所有的石头。具体地，我们可以从起点开始模拟小青蛙的跳跃，每次跳跃能够到达的最远位置为当前位置加上跳跃能力 y，如果这个位置上有石头，则跳跃到这个位置，否则就选择跳到离这个位置最近的、高度不为 0 的石头上。如果能够成功到达终点，则说明当前跳跃能力 y 是可行的，否则就需要增大跳跃能力。

注意到石头的高度会随着小青蛙的跳跃而下降，因此我们需要在模拟跳跃时动态地更新石头高度，同时，为了避免重复模拟，我们可以记录每个石头的最大可达位置，这样在模拟跳跃时就可以直接跳到最远的位置，而不需要每次都重新模拟。

时间复杂度

二分的时间复杂度为 O(logC)，其中 C 表示最大的跳跃能力，每次验证需要模拟一次跳跃，时间复杂度为 O(nlogC)，总时间复杂度为 O(nlogClogC)。

空间复杂度

需要记录每个石头的高度和最大可达位置，空间复杂度为 O(n)。

C++ 代码