1st way. Top-down Divide and Conquer Approach
2nd way. Bottom-up Dynamic Programming Approach
3rd way. Golden Ratio Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <stdlib.h>
#include <math.h>
using namespace std;
class Solution {
public:
    int climbStairs(int n) {
        double estim = 0.4472135955 * pow(1.618033988745, n+1);
        return ( abs(ceil(estim)-estim) < abs(estim-floor(estim)) )? ceil(estim) : floor(estim);
    }
};
int main()
{
   int n = 7;
   Solution s;
   for (int i=0; i <= n; i++)
      cout << "climbStairs(" << i << "): " << s.climbStairs(i) << endl;
   
   return 0;
}