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 。