我要招人

去企业版

首页 > 试题广场 >

跳台阶扩展问题

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

热度指数：12673 时间限制：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

输入

输出

算法知识视频讲解

数据结构和算法

发表于 2022-02-18 21:01:06

解法一这里的青蛙比前面两道题的青蛙更厉害一些，他一次可以跳1阶，2阶，3阶……。所以要想跳到第n个台阶，我们可以从第1个台阶跳上来，也可以从第2个台阶跳上来……，所以递推公式是 f(n)=f(n-1)+f(n-2)+……+f(2)+f(1); 同样如果我们想跳到第n-1个台阶，也可以列出下面这个展开全文

HZU_19_钟伟乐

发表于 2022-03-10 17:41:20

我称之为暴力递归 import java.util.*; public class Main { public static int ppp(int s) { if(s==1||s==0) { return 1; } else if(s<0) { return 0; } el 展开全文

吾亦悠然归山

发表于 2022-07-09 23:14:18

注意题目要求时间复杂度O(1)，那么肯定有一个公式可以直接得出答案。第 1 级台阶，0 级基础上跳 1 级第 2 级台阶，第 1 级基础上跳，0 级基础上跳 2 级第 3 级台阶，第 1 级基础上跳，第 2 级基础上跳，0 级基础上跳 3 级第 4 级台阶，第展开全文

__rookie

发表于 2022-08-03 22:31:43

其实是个数学问题 //思路： //f(n) = f(n-1) + ... + f(1) + 1 //f(1) = 1 //1 2 3 4 5 //1f1 1 展开全文

fred-coder

发表于 2022-02-18 10:49:30

动态规划,由于 n 个台阶可以 1, ... n 都可以调过来,状态转移通过 0, 1, ... n - 1 转移 dp[i] = dp[j] j < i import sys n = int(sys.stdin.readline().strip()) if n == 1: print 展开全文

Sousey

发表于 2022-02-23 17:01:39

跳台阶问题（plus）这个问题看了【数据结构与算法】大佬的操作写出他的状态转移方程： f(n)=f(n-1)+.....f(1) //doge：我只能想到这一步如果跳了一层，剩下n-1层也可如上式： f(n-1) = f(n-2) + .....f(1) 化简可得： f(n) = 2* 展开全文

卖窝瓜的大大怪

发表于 2023-02-24 16:23:44

while 1: try: n = int(input()) dp = [1]*(n+1) for i in range(2, n+1): dp[i] = sum(dp[:i]) print(dp[n]) 展开全文

向光而行的你很犹豫

发表于 2023-05-02 10:32:03

#include<iostream> #include<cmath> using namespace std; int main(){ int n; cin>>n; cout<<pow(2,n-1)<<endl; 展开全文

Galaxy_Lee

发表于 2022-06-24 15:09:34

n = int(input()) lst = [0] * (n+1) if n == 1 or n == 2: pri 展开全文

Pandas_007

发表于 2023-03-26 23:59:41

import sys n = int(input().strip()) dp = [0] * (n+2) dp[0] = 0 dp[1] = 1 dp[2] = 2 #dp[n] = dp[n-1] + dp[n-2] + ... + dp[2] + dp[1] + dp[0] for i in r 展开全文