{ }codelper
dynamic programming64-bit integersP0042

Ways to climb stairs

You climb a staircase of n steps from the bottom (step 0) to the top (step n).
Each move climbs either one step or two steps.
Print the number of different move sequences that land exactly on the top.
For example, for n = 3 there are 3: 1+1+1, 1+2 and 2+1.

Input
1 ≤ n ≤ 70
Output
The number of ways
Example 1 · stdin
3
stdout
3
Example 2 · stdin
50
stdout
20365011074
main.py
Input (stdin)

When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).

$ Ready

Open this on a computer to write and run code. On mobile you can read the problem and the solutions.

In other languagesShow solutions by language · 8 languages

The last move is one step or two, so ways[i] = ways[i-1] + ways[i-2]; fill the table from step 0 and you need only n additions (dynamic programming).
Writing the same formula as plain recursion recomputes the same steps over and over: for n = 70 that is about 10^14 calls and never finishes.
Craykon stops once a run passes about 50 million steps.
The answer is 2,971,215,073 at n = 46, past a 32-bit int (about 2.1 billion), so C, C++, Java and C# need a long/long long table.
The answer for n = 70, 308,061,521,170,129, is below 2^53, so JavaScript, TypeScript and Craykon numbers are exact, and Python integers are unbounded.
Making the table: 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 NewList(n + 1, 0).

Pythonmain.py · 7 lines
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])
JavaScriptmain.js · 6 lines
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]);
TypeScriptmain.ts · 7 lines
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]);
JavaMain.java · 14 lines
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]);    }}
C#Main.cs · 17 lines
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]);    }}
C++main.cpp · 14 lines
#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';}
Cmain.c · 14 lines
#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;}
Craykonmain.cray · 11 lines
n = Console.ReadLine().ToNumber();// ways[i] = i번째 칸까지 오르는 방법 수ways = NewList(n + 1, 0);ways[0] = 1;ways[1] = 1;for (i = 2; i <= n; i++){    // 마지막 걸음이 한 칸 또는 두 칸    ways[i] = ways[i - 1] + ways[i - 2];}Console.WriteLine(ways[n]);