leetcode-climbing stairs

第一种是迭代，第二种是DP，第三种是斐波那契数列的通项公式。

此外，soulmachine的书上还指出，递归也可以，只是速度太慢。

 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 }

https://github.com/soulmachine/leetcode

http://rleetcode.blogspot.com/2014/06/climbing-stairs.html