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
- 1 ≤ n ≤ 80
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
- Your last move was either 1 step (from n − 1) or 2 steps (from n − 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);
}
}