Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Dynamic Programming

Climbing Stairs

Easy · Dynamic Programming · Asked at Amazon, Google, Adobe, TCS, Infosys

You can climb 1 or 2 steps at a time. In how many distinct ways can you reach the top of a staircase with n steps?

Input

One integer n.

Output

The number of ways.

Constraints

ways(n) = ways(n−1) + ways(n−2). The answer for n = 80 needs a 64-bit integer.

Example 1

Input

2

Output

2

Example 2

Input

3

Output

3

Hints

  1. Your last move was either 1 step (from n − 1) or 2 steps (from n − 2).
  2. So ways(n) = ways(n − 1) + ways(n − 2), with ways(1) = 1 and ways(2) = 2 — Fibonacci again. Keep just two variables.

Approach

Every way to reach step n ends with a 1-step from n − 1 or a 2-step from n − 2, and those two groups don't overlap. So ways(n) = ways(n−1) + ways(n−2). Iterate keeping only the last two values. The answer for n = 80 is about 3.8 × 10^16, so use a 64-bit integer.

Complexity: O(n) time · O(1) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long a = 1, b = 1;  // ways(0), ways(1)
    for (int i = 2; i <= n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    cout << b << "\n";
    return 0;
}

Python solution

n = int(input())
a, b = 1, 1  # ways(0), ways(1)
for _ in range(2, n + 1):
    a, b = b, a + b
print(b)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long a = 1, b = 1;  // ways(0), ways(1)
        for (int i = 2; i <= n; i++) {
            long c = a + b;
            a = b;
            b = c;
        }
        System.out.println(b);
    }
}

Solve Climbing Stairs online · All practice problems