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

这是一个经典的动态规划问题。我们可以定义一个长度为 n+1 的数组 dp，其中 dp[i] 表示跳上 i 级台阶的跳法总数。显然 dp[0]=1，dp[1]=1，因为跳上 0 级或 1 级台阶只有一种跳法。对于 i>1 的情况，青蛙可以从 i-1 级或 i-2 级跳上来，因此 dp[i]=dp[i-1]+dp[i-2]。最终答案为 dp[n]。

下面是 Python 代码实现：

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

当 n=40 时，此算法的时间复杂度是 O(n)，可以在短时间内求得答案。

相关问题

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

对于这个问题，我们可以使用动态规划的方法来解决。假设跳上n级台阶的跳法总数为f(n)。

当n=1时，青蛙只有一种跳法，即跳一级台阶。
当n=2时，青蛙有两种跳法，可以一次跳两级，也可以分两次跳一级。
当n>2时，青蛙的第一次跳有两种选择：跳一级或者跳两级。
- 如果青蛙第一次跳一级，那么剩下的台阶数为n-1，此时的跳法总数为f(n-1)。
- 如果青蛙第一次跳两级，那么剩下的台阶数为n-2，此时的跳法总数为f(n-2)。

所以，青蛙跳上n级台阶的总跳法数为f(n) = f(n-1) + f(n-2)。

下面是一个简单的Python程序来求解青蛙跳上n级台阶的总跳法数：

def jumpFloor(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n+1):
        a, b = b, a + b
    return b

n = int(input("请输入台阶数："))
result = jumpFloor(n)
print("青蛙跳上{}级台阶的总跳法数为：{}".format(n, result))

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

### 回答1：
这是一个典型的斐波那契数列问题。设跳上n级台阶的跳法数为f(n)，则有：
f(n) = f(n-1) + f(n-2) (n>2)
初始条件：
f(1) = 1, f(2) = 2
因此，跳上n级台阶的跳法数为f(n)。

### 回答2：
要求青蛙跳上一个n级的台阶总共有多少种跳法，可以采用递归的方式进行求解。

对于青蛙要跳上一个n级的台阶，只有两种情况：
1. 青蛙第一次跳一级，那么剩下的n-1级台阶则有f(n-1)种跳法；
2. 青蛙第一次跳二级，那么剩下的n-2级台阶则有f(n-2)种跳法。

通过分析可以得到，青蛙跳上一个n级的台阶总共有f(n)=f(n-1)+f(n-2)种跳法。

同时可以发现，当n=1时，只有一种跳法；当n=2时，有两种跳法。

因此可以通过递归的方式来求解青蛙跳上一个n级的台阶总共有多少种跳法：
当n>2时，f(n) = f(n-1) + f(n-2)，依次递归求解；
当n=2时，f(n)=2；
当n=1时，f(n)=1。

根据以上的分析，通过递归的方式可以求解青蛙跳上一个n级的台阶总共有多少种跳法。

### 回答3：
这是一个典型的斐波那契数列问题。假设跳上一个n级的台阶的跳法数量为f(n)。

对于第一步，青蛙可以选择跳1级台阶，剩下的问题就变成了跳上n-1级台阶的跳法数量，即f(n-1)；或者选择跳2级台阶，剩下的问题变成了跳上n-2级台阶的跳法数量，即f(n-2)。

所以，青蛙跳上一个n级的台阶的总跳法数量为f(n) = f(n-1) + f(n-2)。

根据初始条件，当n = 1时，青蛙只能跳一次，所以f(1) = 1；当n = 2时，青蛙可以选择跳一次一级台阶两次，或者跳一次两级台阶，所以f(2) = 2。

根据以上递推关系和初始条件，可以使用递归或者迭代的方法求解青蛙跳上一个n级台阶的跳法数量。