```
// fibonacci sequence
int climbStairs(int n) {
if (n <= 2) return n;
int a = 1, b = 2, c = 0;
for (int i = 0; i < n-2; i++){
c = a + b;
a = b;
b = c;
}
return c;
}
// dynamic programming
int climbStairs(int n) {
vector<int> s(n+1);
return f(n, s);
}
int f(int n, vector<int> &s) {
if (s[n]) return s[n];
return s[n] = n <= 2 ? n : f(n-1, s) + f(n-2, s);
}
// decomposition formula
int climbStairs(int n) {
return (pow((1 + sqrt(5)) / 2, n + 1) - pow((1 - sqrt(5)) / 2, n + 1)) / sqrt(5);
}
```