我要招人

去企业版

首页 > 试题广场 >

爬楼梯2

[编程题]爬楼梯2

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

在你面前有一个n阶的楼梯(n>=100且n<500)，你一步只能上1阶或3阶。

请问计算出你可以采用多少种不同的方式爬完这个楼梯（到最后一层为爬完）。

(注意超大数据)

输入描述:

一个正整数，表示这个楼梯一共有多少阶

输出描述:

一个正整数，表示有多少种不同的方式爬完这个楼梯

示例1

输入

输出

24382819596721629

备注:

注意时间限制

算法知识视频讲解

Java

毛涛

采用动态划分算法

使用大整数数组BigInteger[] a 存放已经计算的值

算法公式 a[i] = a[i-1]+a[i-3]

public static BigInteger JumpFloor(int target){
       BigInteger[] a = new BigInteger[target+1];
       a[0] = BigInteger.valueOf(1);
       a[1] = BigInteger.valueOf(1);
       a[2] = BigInteger.valueOf(1);
       a[3] = BigInteger.valueOf(2);
       int i = 4;
       for(i = 4;i<=target;i++) {
           a[i] = a[i-1].add(a[i-3]);
       }
       return a[target];

   }

发表于 2019-08-23 17:25:01 回复(0)

Java

小白201906051502163

public static BigInteger TJ(int n){

    if(n==1||n==2) {
        return BigInteger.valueOf(1);
    }
    if(n==3) {
        return BigInteger.valueOf(2);
    }
    BigInteger a=BigInteger.valueOf(1);
    BigInteger b=BigInteger.valueOf(1);
    BigInteger c=BigInteger.valueOf(2);
    BigInteger temp=BigInteger.valueOf(0);
    for(int i=n;i>3;i--) {
        temp=a.add(c);
        a=b;
        b=c;
        c=temp;
    }
    return temp;
}

发表于 2019-08-16 10:44:10 回复(1)

Java

谁的电脑

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        BigInteger[] count = new BigInteger[n];
        count[0] = new BigInteger("1");
        count[1] = new BigInteger("1");
        count[2] = new BigInteger("2");
        for (int i = 3; i < n; i++) {
            count[i] = count[i - 1].add(count[i - 3]);
        }
        System.out.println(count[n - 1]);
    }
}

编辑于 2019-07-15 17:02:40 回复(4)

提交观点

问题信息

动态规划运维工程师小米集团 2019 递归

来自：小米2019秋招运维工...

上传者：小小

难度：

3条回答 36收藏 9322浏览

通过挑战的用户

查看代码

牛客15886...

2022-09-22 18:27:36
ray_yan2

2022-09-14 16:29:48
牛客zhangtr

2022-09-13 10:44:29
莫茗丶

2022-09-11 10:45:22
乾之爻三

2022-09-11 08:33:07

爬楼梯2

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题