1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4  5 class Solution { 6 public: 7     int climbStairs(int n) { 8         int prev = 0; 9         int cur = 1;10         for (int i = 1; i <= n; i++)11         {12             int tmp = cur;13             cur += prev;14             prev = tmp;15         }16         return cur;17     }18 };19 class Solution2 {20 public:21     int climbStairs(int n) {22         int* dp = new int[n + 1];23         dp[1] = 1; dp[0] = 1;24         for (int i = 2; i <= n; i++)25         {26             dp[i] = dp[i - 1] + dp[i - 2];27         }28         return dp[n];29     }30 };31 class Solution3 {//attention: we should calculate a[n+1] instead of a[n]!!!because a[1]=1,a[2]=1!!!32 public:33     int climbStairs(int n) {34         int result;35         double s = sqrt(5);36         result = (1 / s)*(pow((1 + s) / 2, n + 1) - pow((1 - s) / 2, n + 1));37         return result;38     }39 };40 41 int main()42 {43     //Solution s;44     //Solution2 s;45     Solution3 s;46     cout << s.climbStairs(8) << endl;47     return 0;48 }