首页 > 试题广场 >

跳台阶扩展问题

[编程题]跳台阶扩展问题
  • 热度指数：15261 时间限制：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)
C++
Man9o头像 Man9o

DFS

自上而下地将大问题分解为规模更小但性质相同的小问题，对于第i个台阶，它可以从i-1跳上来，也可以从i-2跳上来，...，直到第一个台阶跳上来。

例如dfs(4)：

dfs(3)=dfs(2)+dfs(1)
       dfs(2)=dfs(1)
              dfs(1)=dfs(0)=1

因此

dfs(3)=dfs(0)+dfs(0)+dfs(0)+dfs(0)=4

定义dfs(i)表示调到第i个台阶的总跳法，i从1开始，那么边界就是当i=0时，表示找到了一组答案，返回1。

代码

#include <iostream>
using namespace std;
int n;
int dfs(int i)
{
    if (i == 0) return 1;
    int res = 0;
    for (int j = 1; j <= i; j++)
        res += dfs(i - j);
    return res;
}

int main()
{
    cin >> n;
    cout << dfs(n) << endl;
    return 0;
}
发表于 2024-08-14 17:03:23 回复(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)
Php
酷爱喝粥得馒头仔头像 酷爱喝粥得馒头仔
<?php
while(fscanf(STDIN, "%d", $a) == 1)
        echo getCount($a)."\n";

    function getCount($num, $sumCount = 0) {
        if ($num - 1 == 0) {
            return 1 + $sumCount;
        } else {
            return getCount($num - 1, getCount($num - 1) + $sumCount);
        }
    }
发表于 2025-06-17 14:35:06 回复(0)
Python3
炼0805头像 炼0805 
n = int(input())
print(pow(2,n-1))

发表于 2025-05-08 14:43:44 回复(0)
Java
JohnSm1th头像 JohnSm1th
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=in.nextInt();
        int ans=0,cur=0;
        for(int i=1;i<n;i++)
        {
            cur=ans+1;
            ans+=cur;
        }
        System.out.println(ans+1);

    }
}
发表于 2024-08-15 15:27:26 回复(0)
牛客742471788号头像 牛客742471788号
简单粗暴 
#include <stdio.h>
int main() {
    int a;
    scanf("%d", &a);
    printf("%d\n", 1<<(a-1));
    return 0;
}




发表于 2024-06-13 23:34:18 回复(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)
Bule_Dragon头像 Bule_Dragon

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)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

跳台阶扩展问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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