跳台阶扩展问题

[编程题]跳台阶扩展问题

热度指数：12683 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

数据范围： $1 \le n \le 20$
进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(1)$

输入描述:

本题输入仅一行，即一个整数 n

输出描述:

输出跳上 n 级台阶的跳法

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

Python 3

牛客嗷嗷

这里的青蛙比前面两道题的青蛙更厉害一些，他一次可以跳1阶，2阶，3阶……。所以要想跳到第n个台阶，我们可以从第1个台阶跳上来，也可以从第2个台阶跳上来……，所以递推公式是

f(n)=f(n-1)+f(n-2)+……+f(2)+f(1);

即：f(n)=2^(n-1)

n = int(input())
print(2 ** (n - 1))

发表于 2022-09-13 14:45:52 回复(0)

Python 3

牛客103204480号

# f(n) = f(n-1) + f(n-2) + .... + f(2) + f(1)
# f(n-1) = f(n-2) + .... + f(1)
# f(n) - f(n-1) = f(n-1) => f(n) = 2 * f(n-1)

def jumpII(n):
    if n == 1:
        return 1
    else:
        return 2*jumpII(n-1)

n = int(input())

dp = [0, 1]

for i in range(2, n+1):
    dp.append(2*dp[i-1])
print(dp[n])

发表于 2022-08-12 15:55:15 回复(0)

Python 3

麓南的风

#当输入n时求f(n)

#第n个台阶，跳法有从n-1跳上去，也可以从n-2...3,2,1,0(底层）一次跳上去

#那么f（n）=f(n-1) + f(n-2) + ...+ f(2) + f(1) + f(0)

#结束条件，f(0) = 0,f(1)=1,f(2)=2

n = int(input())
def func(n):
    if n == 0:
        return 0 
    if n ==1:
        return 1
    if n == 2:
        return 2
    if n > 2:
        return 2*func(n-1)
print(func(n))

发表于 2022-08-09 10:42:53 回复(0)

Python 3