首页 > 试题广场 >

跳台阶

[编程题]跳台阶

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

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围： $0 \leq n \leq 40$

要求：时间复杂度： $O(n)$ ，空间复杂度： $O(1)$

输入描述:

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

输出描述:

输出跳上 n 级台阶有多少种跳法

示例1

输入

输出

说明

青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2

示例2

输入

输出

算法知识视频讲解

Java

牛客622123437号

import java.util.Scanner;
public class Main{
public static int func(int n){
if(n==1)
return 1;
if(n==2)
return 2;
return func(n-1)+func(n-2);
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int ret=func(n);
System.out.println(ret);
}
}

发表于 2022-06-23 15:49:10 回复(0)

君阮池

#include <stdio.h>

int jump(int x)
{
    if(x<=2)
       return x;
    else
       return jump( x - 1 ) + jump( x - 2 ); 
}
int main() 
{
    int n = 0; 
    scanf("%d",&n);
    printf("%d\n",jump(n));
   
    return 0;
}

发表于 2023-07-10 16:23:35 回复(0)

wang9

#include <stdio.h>
int count(int n) {
    int count1;
    if (1 == n) {
        count1 = 1;
    } else {
        if (2 == n) {
            count1 = 2;
        } else {
            count1 = count(n - 2) + count(n - 1);
        }
    }
    return count1;
}
int main() {
    int n = 0;
    scanf("%d", &n);
    printf("%d", count(n));
    return 0;
}

发表于 2023-03-19 15:24:07 回复(0)

Python3

池中物_2024

n = int(input())
if n <= 2:
    print(n)
else:
    pre1 = 1
    pre2 = 2
    res = 0
    n -= 2
    while n:
        res = pre1 + pre2
        pre1 = pre2
        pre2 = res
        n -= 1
    print(res)

发表于 2023-01-06 13:45:26 回复(0)

C++

Spectre_

#include <iostream>
using namespace std;

int main() {
    int number;
    cin >> number;
    // 时间复杂度O(N)，空间复杂度O(1)
    if (number < 3) {
        cout << number;
        return 0;
    }
    int dp1 = 1, dp2 = 2, dp3;
    for (int i = 3; i <= number; ++i) {
        dp3 = dp1 + dp2;
        dp1 = dp2;
        dp2 = dp3;
    }
    cout << dp3;
    return 0;
}

发表于 2022-10-30 20:46:51 回复(0)

Python 3

牛客嗷嗷

a, b = 1, 1
n = int(input())
for _ in range(n):
    a, b = b, a + b
print(a)

发表于 2022-09-13 14:42:31 回复(0)

C++

吾亦悠然归山

#include <iostream>
using namespace std;

int f(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else if (n == 2) {
        return 2;
    }
    int f1 = 1, f2 = 2, f3 = 3;
    for (int i = 3; i <= n; i++) {
        f3 = f1 + f2;
        f1 = f2;
        f2 = f3;
    }
    return f3;
}

int main() {
    int n;
    cin >> n;
    cout << f(n);
    return 0;
}

发表于 2022-03-02 19:28:05 回复(0)

Java

有胆量的可乐不愿吃饼

import java.math.BigInteger;
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();
            BigInteger count = BigInteger.valueOf(1);
            for (int i = 0; i < a; i++) {
                if ((a - i) % 2 == 0) {
                    if (i > 0) {
                    //数学的排列组合公式：排列总个数的阶乘/每个元素个数阶乘的乘积
                        count = count.add(jc(i + (a - i) / 2).divide(jc(i).multiply(jc((a - i) / 2))));
                    } else {
                        count = count.add(BigInteger.valueOf(1));
                    }

                }
            }
            System.out.println(count);
        }
    }

    /**阶乘
     */
    private static BigInteger jc(int num) {
        BigInteger count = BigInteger.valueOf(num);
        for (int i = num - 1; i > 1; i-- ) {
            count = count.multiply(BigInteger.valueOf(i));
        }
        return count;
    }
}

编辑于 2024-04-08 14:27:43 回复(0)

matlab

LuckyYing

clc

clear

N_ladder = input(''); % 查询的 n 级台阶

if N_ladder == 1

fprintf('%d', 1)

elseif N_ladder == 2

fprintf('%d', 2)

elseif N_ladder >= 3

dp_i_2 = 1;

dp_i_1 = 2;

for i = 3:N_ladder

dp_i = dp_i_1 + dp_i_2; % 状态转移方程

dp_i_2 = dp_i_1; % 更新顺序是有讲究的

dp_i_1 = dp_i;

end

fprintf('%d', dp_i)

end

编辑于 2024-01-27 15:21:47 回复(0)

大数据23102陈宏禹

#include<stdio.h>

int main()

{ int f=1,d=2,n,j=0,i;

scanf("%d",&n);

if(n==1)

printf("%d",f);

if(n==2)

printf("%d",d);

if(n>=3)

{ for(i=3;i<=n;i++)

{ j=f+d;

f=d;

d=j;

}

printf("%d",j);

}

return 0;

}

编辑于 2023-12-05 17:18:12 回复(0)

牛客290122925号

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 num = getStairsNum(a);

System.out.println(num);

}

public static int getStairsNum(int n) {

int[] dp = new int[2];

dp[0] = 0;

dp[1] = 1;

for(int i = 0; i < n; i++) {

int sum = dp[1] + dp[0];

dp[0] = dp[1];

dp[1] = sum;

}

return dp[1];

}

发表于 2023-10-19 17:02:56 回复(0)

C++

_Blossom_

#include <cstdio>

#include <iostream>

using namespace std;

int frog(int n){

if(n==1||n==0) return 1;

else return frog(n-1)+frog(n-2);

}

int main() {

int n;

scanf("%d",&n);

printf("%d",frog(n));

}

// 64 位输出请用 printf("%lld")

发表于 2023-08-18 19:25:12 回复(0)

代码太难写

#include <stdio.h>

int f(int n)

{

int f[41];

f[0] =f[1] = 1;

for(int i = 2;i<=n;i++)

{

f[i] = f[i-1]+f[i-2];

}

return f[n];

}

int main() {

int in;

scanf("%d",&in);

printf("%d",f(in));

}

发表于 2023-04-22 10:44:25 回复(0)

化骨重生

import sys

n=int(input())

#a代表n=i-1时以1步结尾的走法数 b代表n=i-1时以2步结尾的走法数

#有这样的关系：

#1、n=i时以1步结尾的走法数为原来的a+b

#2、b代表n=i-1时以2步结尾的走法数为原来的a（这里用来保存上一次的a）

a=0#初始a=0 b=1刚好满足计算n=1时的条件

b=1

for i in range(1,n+1):

m=a

a=a+b

b=m

#最后的a为n级台阶时以1步结尾的走法数 b代表n级台阶时以2步结尾的走法数

#合起来就是总的走法数

print(a+b)

发表于 2023-04-16 21:35:11 回复(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++) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}
		System.out.println(dp[n]);
		scan.close();
	}

发表于 2023-04-13 21:27:54 回复(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 = in.nextInt();
        int result = GetNum(n);
        System.out.print(result);
    }
    public static int GetNum(int n){
        if(n < 3){
            return n;
        }
        int[] dp = new int[n+1];//创建数组
        //确定其推公式dp[i] = dp[i-1]+dp[i-1]
        //初始化
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3;i<=n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];

    }
}

发表于 2023-02-28 13:31:15 回复(0)

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var n int
    fmt.Scanf("%d",&n)
    if n<=2{
        fmt.Println(n)
        return
    }
    p,q,r:=1,2,3
    for i:=4;i<=n;i++{
        p=q
        q=r
        r=p+q
    }
    fmt.Println(r)
}

发表于 2023-02-04 10:21:41 回复(0)

C++

牛客238088962号

不懂就问，题目要求空间复杂度为O(1）为什么我用了长度为n的数组(数组长度为n，空间复杂度不就是o（n)了吗），居然也对了

发表于 2022-10-23 13:04:23 回复(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 || num == 2){
                System.out.println(num);
                return;
            }
            arr[1] = 1;
            arr[2] = 2;
            for(int i = 3;i <= num;i++){
                arr[i] = arr[i - 2] + arr[i - 1];
            }
            System.out.println(arr[num]);
        }
    }
}

发表于 2022-09-23 11:19:21 回复(0)

Python 3

踏实的大白菜说又不是不能用

def solution(n):
    dp = [0]*(n+1)
    if n <=2 :
        return n
    dp[1] = 1
    dp[2] = 2
    for i in range(3,n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]
a = int(input())
print(solution(a))

发表于 2022-09-08 16:37:29 回复(0)

提交观点

问题信息

动态规划记忆化搜索递归

难度：

40条回答 34收藏 2084浏览

通过挑战的用户

查看代码

牛客82144...

2022-10-23 17:38:24
不摆烂不会摆烂

2022-09-22 10:46:55
牛客53155...

2022-09-16 14:18:32
枺翳

2022-09-15 23:37:18
牛客42043...

2022-09-15 22:37:57

跳台阶

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题