爬楼梯

[编程题]爬楼梯

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

在你面前有一个n阶的楼梯，你一步只能上1阶或2阶。
请问计算出你可以采用多少种不同的方式爬完这个楼梯。

输入描述:

一个正整数n(n<=100)，表示这个楼梯一共有多少阶

输出描述:

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

示例1

输入

输出

算法知识视频讲解

Java

等一个offer的河老师很想踩缝纫机

import java.math.BigDecimal;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int sum = in.nextInt();
        if (sum == 1) {
            System.out.println(1);
            return;
        } else if (sum == 2) {
            System.out.println(2);
            return;
        } else if (sum <= 0) {
            System.out.println();
            return;
        }
        BigDecimal[] ary = new BigDecimal[sum];
        ary[0] = BigDecimal.valueOf(1);
        ary[1] = BigDecimal.valueOf(2);
        for (int i = 2; i < sum; i++) {
            ary[i] = ary[i - 2].add(ary[i - 1]);
        }
        System.out.println(ary[sum - 1].toString());
    }
}

发表于 2023-02-17 15:56:49 回复(0)

Java

RanYe_749815285

本题结果用long类型存放也会超出范围，只能使用字符串存放。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] dp = new String[101]; // 楼梯的台阶数小于等于100
        dp[1] = String.valueOf(1);
        dp[2] = String.valueOf(2);
        for (int i = 3; i <= 100; i++) {
            dp[i] = add(dp[i - 1], dp[i - 2]); // 两个字符串相加
        }

        int n = sc.nextInt();
        System.out.println(dp[n]);
    }

    public static String add(String s1, String s2) {
        int n1 = s1.length() - 1;
        int n2 = s2.length() - 1;
        int add = 0; // 记录进位
        StringBuffer sb = new StringBuffer(); // 存放结果
        while (n1 >= 0 || n2 >= 0) {
            int x = (n1 >= 0) ? s1.charAt(n1) - '0' : 0;
            int y = (n2 >= 0) ? s2.charAt(n2) - '0' : 0;
            int sum = x + y + add;
            if (sum > 9) {
                sb.insert(0, sum % 10);
                add = 1;
            } else {
                sb.insert(0, sum);
                add = 0;
            }
            n1--;
            n2--;
        }
        if (add == 1) sb.insert(0, 1); // 最后查看是否有进位
        return sb.toString();
    }
}

发表于 2021-09-09 21:45:39 回复(0)

Java

徐瑾麓

import java.util.*;
import java.math.BigInteger;
public class Main{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
BigInteger[] a = new BigInteger[n+1];
if(n<3) System.out.println(n);
if(n>=3){
a[1]=new BigInteger("1");
a[2]=new BigInteger("2");
for(int i = 3;i<=n;i++){
a[i]=a[i-1].add(a[i-2]);
}
System.out.println(a[n]);
}
}
}

发表于 2021-09-07 20:52:59 回复(0)

Java

瑾言i

package com.digui;

import java.math.BigInteger;
import java.util.Scanner;

public class Main{
	
    public static BigInteger Jump(int n){
    	
    	BigInteger t = BigInteger.valueOf(0);
       if(n==1||n==2){
    	   return BigInteger.valueOf(n);
       }
       if(n>=3){
    	   BigInteger prev_2=BigInteger.valueOf(1);
    	   BigInteger prev_1=BigInteger.valueOf(2);
    	   
    	   for(int i=3;i<=n;i++){
    		   t = prev_1.add(prev_2);
    		   prev_2 = prev_1;
    		   prev_1=t;
    		   
    	   }
    	   return t;
       }
    	return t;
   }
    
   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);
       int n = scanner.nextInt();
       System.out.println(Jump(n));
   }

}
//特别要注意时间和空间的问题，若用递归解，时间复杂度是2^n即2的n次幂
//空间则要注意数据类型内存的溢出问题

编辑于 2019-10-23 15:42:56 回复(0)

Java

飒飒的收到Z传说中

不知道能不能用BigInteger，反正我用了。

import java.util.Scanner;
import java.math.BigInteger;
public class Main{
        public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
                int n = sc.nextInt();
                System.out.println(jumpFloor(n));
        }
        public static BigInteger jumpFloor(int n){
                if(n<3) return BigInteger.valueOf(n==1?1:2);
                BigInteger res= BigInteger.valueOf(0);
                BigInteger res1= BigInteger.valueOf(1);
                BigInteger res2= BigInteger.valueOf(2);
                for(int i=3;i<=n;i++){
                        res=res1.add(res2);
                        res1=res2;
                        res2=res;
                }
                return res;
        }
}

发表于 2019-09-02 13:51:21 回复(0)

Java

谁的电脑

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        ArrayList<BigInteger> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            BigInteger temp = (i <= 2) ? BigInteger.valueOf(i) : list.get(i - 2).add(list.get(i - 3));
            list.add(temp);
        }
        System.out.println(list.get(list.size() - 1));
    }
}

发表于 2019-07-08 16:16:43 回复(0)