在你面前有一个n阶的楼梯,你一步只能上1阶或2阶。
请问计算出你可以采用多少种不同的方式爬完这个楼梯。
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()); } }
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(); } }
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次幂 //空间则要注意数据类型内存的溢出问题
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; } }
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)); } }