LeetCode Online Judge 题目C# 练习 - Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

解法1 - 递归：

1         public static int ClimbStairsRecursive(int n)
2         {
3             if (n <= 2)
4                 return n;
5             return ClimbStairsRecursive(n - 2) + ClimbStairsRecursive(n - 1);
6         }

解法2 - DP：

 1         public static int ClimbStairsDP(int n)
 2         {
 3             int[] s = { 0, 1, 2 };
 4             if(n <= 2)
 5                 return s[n];
 6 
 7             int num = 2;
 8 
 9             while (num++ < n)
10             {
11                 s[num % 3] = s[(num + 1) % 3] + s[(num + 2) % 3];
12             }
13 
14             return s[n % 3];
15         }

代码分析：

这其实就是一个fibonacci数列， k(n) = k(n-1) + k(n-2); k(0) = 0; k(1) = 1; 当然在这题里 k(2) = 2 (两步的阶梯可以分为两种走法)。

解法一用的是递归。简单！

解法二用的是DP（dynamic programming)，为了减低空间复杂度，我只用了一个3个元素的数组。如果建一个int[n]的数组，空间复杂度就为O(n)了，现在是是constant space。DP的performance（效率）一定是比recursive 来的快的，因为每次递归都要新建stack。下面看看测试不同解法的performace。

1             Stopwatch watch = new Stopwatch();
2             watch.Start();
3             for (int i = 0; i < 10; i++) 
4                 Console.WriteLine(ClimbStairsDP(30));
5                 //Console.WriteLine(ClimbStairsRecursive(30));
6             watch.Stop();
7             Console.WriteLine(watch.ElapsedMilliseconds);

我就不插图了，告诉大家结果。在我的机器上 Recursive 使用时间270ms左右， DP 使用时间 0 - 1ms 。