7-1 青蛙跳台阶 动态规划

好的，我知道了。那么，7-1 青蛙跳台阶问题是指：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法。

这是一个经典的动态规划问题。我们可以用dp[i]表示跳上i级台阶的跳法总数，那么状态转移方程为：

dp[i] = dp[i-1] + dp[i-2]
边界条件为dp=1, dp=1。

最终答案为dp[n]。

代码如下：

def jumpFloor(n):
    if n == 0 or 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]

相关问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

这是一个经典的斐波那契数列问题，可以使用动态规划求解。设 $dp_i$ 表示跳上第 $i$ 级台阶的跳法总数，则有状态转移方程 $dp_i = dp_{i-1} + dp_{i-2}$，初始条件为 $dp_0 = dp_1 = 1$。由于最终答案需要取模，因此在每次转移时需要取模。具体实现代码如下：

def jump(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
    return dp[n] if dp[n] < 1000000007 else 1

需要注意的是，如果最终答案为 $1000000008$，则需要返回 $1$。

写个程序：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n级的台阶总共有多少种跳法。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

好的，以下是 Python 代码实现：

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

n = int(input())
print(jumpFloor(n))

在这个程序中，我们使用了动态规划的思想来解决这个问题。当台阶数为 1 或 2 时，跳法分别为 1 和 2，直接返回即可。当台阶数大于 2 时，我们使用两个变量 a 和 b 来保存前两个状态的跳法数，然后从 3 开始迭代计算每个状态的跳法数，并用 b 来保存当前状态的跳法数。最后返回 b 对 1000000007 取模的结果即可。

需要注意的是，由于题目要求对结果取模，因此在计算过程中要不断取模，否则可能会出现整型溢出的情况。同时，如果最终结果为 1000000008，需要返回 1。