一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
数据范围:
要求:时间复杂度: ,空间复杂度:
本题输入仅一行,即一个整数 n
输出跳上 n 级台阶有多少种跳法
2
2
青蛙要跳上两级台阶有两种跳法,分别是:先跳一级,再跳一级或者直接跳两级。因此答案为2
7
21
#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; }
#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; }
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; } }
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(); }
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]; } }
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]); } } }
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))