#51 Hard Advanced

DP: Climbing Stairs

Open the editor

Problem

Count ways to climb n stairs with 1 or 2 steps.

Constraints

1 <= n <= 10^6

Hints

1
Fibonacci DP
2
O(n)

Worked solution

Reference solution

One correct implementation. Alternative approaches that satisfy the constraints are equally valid — the reviewer judges behaviour, not style.

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

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