爬楼梯的方法数
从最底下（第 0 级）爬到 n 级楼梯的顶端（第 n 级）。
每一步可以上一级或两级。
输出恰好到达顶端的不同走法数。
例如 n = 3 时有 1+1+1、1+2、2+1 共 3 种。
- 输入
- 1 ≤ n ≤ 70
- 输出
- 走法数
3
3
50
20365011074
错误列表00F8 ↓ · ⇧F8 ↑
输入(stdin)
运行时这些行会依次作为 input()/标准输入传入(运行中不会等待输入)。
$ 就绪
请在电脑上打开以编写和运行代码。在手机上可以查看题目和题解。
其他语言怎么写？查看各语言题解 · 8 种语言题解
最后一步不是一级就是两级，所以 ways[i] = ways[i-1] + ways[i-2]；从第 0 级开始填表，只需做 n 次加法（动态规划）。
若把同一公式直接写成递归，会一遍又一遍地重算同样的台阶，n = 70 时调用约 10^14 次，根本算不完——Craykon 在执行步数超过约 5 千万次时会停止。
n = 46 时答案为 2,971,215,073，超过 32 位 int（约 21 亿），所以 C、C++、Java、C# 需要 long/long long 的表。
n = 70 的答案 308,061,521,170,129 小于 2^53，JavaScript、TypeScript、Craykon 的数也能精确表示，Python 则没有上限。
建表：Python [0] * (n + 1)，JavaScript new Array(n + 1).fill(0)，Java、C# new long[n + 1]，C++ std::vector<long long>(n + 1)，Craykon 新列表(n + 1, 0)。
n = int(input())ways = [0] * (n + 1) # ways[i] = i번째 칸까지 오르는 방법 수ways[0] = 1ways[1] = 1for i in range(2, n + 1): ways[i] = ways[i - 1] + ways[i - 2] # 마지막 걸음이 한 칸 또는 두 칸print(ways[n])const n = Number(require("fs").readFileSync(0, "utf8").trim());const ways = new Array(n + 1).fill(0); // ways[i] = i번째 칸까지 오르는 방법 수ways[0] = 1;ways[1] = 1;for (let i = 2; i <= n; i++) ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸console.log(ways[n]);import { readFileSync } from "node:fs";const n: number = Number(readFileSync(0, "utf8").trim());const ways: number[] = new Array(n + 1).fill(0); // ways[i] = i번째 칸까지 오르는 방법 수ways[0] = 1;ways[1] = 1;for (let i = 2; i <= n; i++) ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸console.log(ways[n]);import java.util.Scanner; public class Main { public static void main(String[] args) { int n = new Scanner(System.in).nextInt(); long[] ways = new long[n + 1]; // ways[i] = i번째 칸까지 오르는 방법 수 ways[0] = 1; ways[1] = 1; for (int i = 2; i <= n; i++) { ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸 } System.out.println(ways[n]); }}using System; class Program{ static void Main() { int n = int.Parse(Console.ReadLine().Trim()); long[] ways = new long[n + 1]; // ways[i] = i번째 칸까지 오르는 방법 수 ways[0] = 1; ways[1] = 1; for (int i = 2; i <= n; i++) { ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸 } Console.WriteLine(ways[n]); }}#include <iostream>#include <vector> int main() { int n; std::cin >> n; std::vector<long long> ways(n + 1); // ways[i] = i번째 칸까지 오르는 방법 수 ways[0] = 1; ways[1] = 1; for (int i = 2; i <= n; i++) { ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸 } std::cout << ways[n] << '\n';}#include <stdio.h> int main(void) { int n; scanf("%d", &n); long long ways[71]; // ways[i] = i번째 칸까지 오르는 방법 수 ways[0] = 1; ways[1] = 1; for (int i = 2; i <= n; i++) { ways[i] = ways[i - 1] + ways[i - 2]; // 마지막 걸음이 한 칸 또는 두 칸 } printf("%lld\n", ways[n]); return 0;}n = 控制台.读行().转数字();// ways[i] = i번째 칸까지 오르는 방법 수ways = 新列表(n + 1, 0);ways[0] = 1;ways[1] = 1;循环 (i = 2; i <= n; i++){ // 마지막 걸음이 한 칸 또는 두 칸 ways[i] = ways[i - 1] + ways[i - 2];}控制台.输出(ways[n]);