首页 > 试题广场 >

跳台阶扩展问题

[编程题]跳台阶扩展问题
  • 热度指数：12600 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

数据范围：
进阶：空间复杂度 ， 时间复杂度

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


输出描述:
输出跳上 n 级台阶的跳法
示例1

输入

3

输出

4
示例2

输入

1

输出

1
算法知识视频讲解
添加回答
牛客520715510号头像 牛客520715510号
状态转移方程为F(n)=pow(2,n-1);
发表于 2022-02-13 11:28:45 回复(0)
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)
化骨重生头像 化骨重生
import sys
#将n级楼梯的跳法分成n类，分别是以跳1,2,3,...,n步为最后一步
#sum（i）表示为n=i时的总走法数 dp[i]表示以i为最后一步的走法数
#故sum(i)=dp[1]+dp[2]+...+dp[i-1]+dp[i]

#n=i 与n=i-1的关系
#n=i时：
#可以将n=i-1的所有跳法后面添一个1看作最后一步为1 此时n为i时的dp[1]=sum(i-1)
#而n=i以2作为最后一步的走法数等于n=i-1时以1作为最后一步的走法数 此时(n为i时的dp[2])=(n为i时的dp[1])
#...
#...
#而n=i以i为最后一步的走法数等于n=i-1时以i-1作为最后一步的走法数 此时(n为i时的dp[i])=(n为i-1时的dp[1])
#以此类推
#得sum(i)=dp[1]+dp[2]+...+dp[i-1]+dp[i]=sum(i-1)*2
#所以n每加1走法数就乘2 n=1时走法数为1 所以n=n时走法数为2**（n-1）
n=int(input())
print(2**(n-1))


发表于 2023-04-17 00:40:29 回复(0)
C++
Spectre_头像 Spectre_ 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    // 时间复杂度O(N)，空间复杂度O(1)。如果使用pow(2, n - 1)，时间复杂度O(1)
    int pre = 1, cur = 1;
    for (int i = 2; i <= n; ++i) {
        cur = pre + 1;
        pre += cur;
    }
    cout << cur;
    return 0;
}

发表于 2022-10-30 20:45:04 回复(0)
Python3
月下飛天鏡头像 月下飛天鏡
首项为 1，公比为 2 的等比数列： 
n = int(input())
print(2 ** (n - 1))


发表于 2024-03-01 13:38:51 回复(0)
matlab
LuckyYing头像 LuckyYing
clc
clear

 N = input('');                             % N台阶

fprintf('%d', 2^(N-1))                      % 满足 空间复杂度 O(N)
发表于 2024-01-27 15:35:07 回复(0)
C++
白罗罗头像 白罗罗
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin>>n;
    int a[20];
    for(int i=0;i<=n;i++)
    {
        a[i]=0;
    }
    a[0]=1;
    a[1]=1;
    a[2]=2;
    for(int i=3;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {
            a[i]=a[i]+a[j];
        }
    }
    cout<<a[n];
   
    return 0;
   
}
发表于 2023-09-16 13:21:36 回复(0)
ZEILEN头像 ZEILEN
int main() {
    int i;
    scanf("%d",&i);
    i = 1<<(i - 1);
    printf("%d",i);
    return 0;
}
发表于 2023-09-08 23:06:25 回复(0)
C
君阮池头像 君阮池 
#include <stdio.h>
int jump(int x)
{
    int a = 1;
    int b = 1;
    int count = 1;
    if (x <= 2)
        count = x;
    else
    {
        for (a = x - 1; a > 0; a--)
        {
            b += jump(a);
        }
        count = b;
    }
    return count;
}

int main()
{
    int n = 0;
    scanf("%d", &n);
    printf("%d\n", jump(n));

    return 0;
}

发表于 2023-07-11 17:04:25 回复(0)
牛客441771659号头像 牛客441771659号

f(0)=1
含义:走到第 0 级台阶有一种方法,每增加一级台阶,小青蛙的跳跃能力就多了一种

发表于 2023-05-16 10:30:16 回复(0)
梁山教父头像 梁山教父 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n=0;
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            n = in.nextInt();
        }
        if(n==1||n==2){
            System.out.println(n);
            return;
        }
        int dp[]=new int[n+1];
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            for(int j=1;j<i;j++){
                dp[i]+=dp[j];
            }
            dp[i]+=1;
        }
        System.out.println(dp[n]);
    }
}

发表于 2023-05-13 10:12:51 回复(0)
呼延棋大宝头像 呼延棋大宝 
n = int(input())
print(pow(2,n-1))

发表于 2023-04-21 13:05:14 回复(0)
不太可爱的程序猪头像 不太可爱的程序猪 
public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] dp = new int[n+2];
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;
		for(int i = 3;i < dp.length;i++) {
			for(int j = 0;j < i;j++) {
				dp[i] = dp[i] + dp[j];
			}
			//加上1到n的
			dp[i] = dp[i] + 1;
		}
		System.out.println(dp[n]);
	}

发表于 2023-04-14 19:59:57 回复(0)
Go
小谷围做题家头像 小谷围做题家 
package main

import (
    "fmt"
)

func main() {
    var n int
    fmt.Scanf("%d",&n)
    fmt.Println(calc(n))
}

func calc(n int)int{
    if n==1{
        return 1
    }
    return calc(n-1)*2
}

发表于 2023-02-05 15:14:13 回复(0)
C++
麻烦忍一忍头像 麻烦忍一忍
#include <iostream>
using namespace std;
int taijie(int n){
    if ((n==1)) {
    return  1;
    }
    else {
     return  2*taijie((n-1));
    }
}
int main() {
    int n;
    cin>>n;
    cout<<taijie((n));
}
发表于 2023-01-16 12:40:16 回复(0)
Java
努力学习ing！！头像 努力学习ing！！ 
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int n = Integer.parseInt(s);
        int ans = 1 << (n-1);
        System.out.println(ans);
    }
}

发表于 2022-10-03 14:27:02 回复(0)
Java
圣光·明流火头像 圣光·明流火 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            /*int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(a + b);*/
            int num = in.nextInt();
            int arr[] = new int[num + 1];
            if(num == 1){
                System.out.println(num);
                return;
            }
            //等比数列
            //f(n) = f(n-1) + f(n-2) + ....+1
            //因为f(n-1) = f(n-2) + f(n-3) + ....+1
            //所以f(n) = f(n-1) + f(n-1)=2f(n-1)
            System.out.println((int)Math.pow(2,num - 1));
        }
    }
}

发表于 2022-09-23 11:31:50 回复(0)
Javascript_V8
LivingRose头像 LivingRose 
while(n = +readline()){
    console.log(add(n));
}
function add(n){
    if(n==0){
        return 0;
    }else if(n ==1){
        return 1
    }else if(n==2){
        return 2;
    }else{
        return 2*add(n-1)
    }
}

发表于 2022-09-05 15:39:30 回复(1)
JavaScript V8
怕浪猫头像 怕浪猫

递归

function skip(x) {
  if(x == 1) return 1
  return 2 * skip(x - 1)
}
console.log(skip(readline()));

动态规划

function skip(x) {
  let dp = Array(x + 1).fill(0);
  if (x == 1) return 1;
  if (x == 2) return 2;
  dp[0] = 1;
  dp[1] = 1;
  dp[2] = 2;
  for (let i = 3; i < x + 1; i++) {
    for (let j = 0; j < i; j++) {
      dp[i] += dp[j];
    }
  }
  return dp[x];
}
let n = parseInt(readline());
console.log(skip(n));
发表于 2022-08-31 00:25:05 回复(0)
C++
牛客241103362号头像 牛客241103362号 
#include<iostream>
#include<cmath>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int dp[20]{0};
    
    dp[0]=1;
    dp[1]=1;
    dp[2]=2;
    
    for(int i=3;i<=n;i++)
    {
        for(int j=0;j<i;j++)
        {
            dp[i]=dp[i]+dp[j];
        }
    }
    
    
    cout<<dp[n];
    
    
    return 0;
}

发表于 2022-08-20 23:32:23 回复(0)
提交观点

问题信息

动态规划 记忆化搜索 递归
难度：
38条回答 2579浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号