LeetCode -- Climbing Stairs

LeetCode -- 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?


就是有n階樓梯，求出不同上法的次數，每次只能上1或2階樓梯。


要求上樓梯的情況數，即求下樓梯的情況數，即對於n階樓梯的下樓情況數來說，相當於先下一階和先下兩階的情況數之和，即：
ClimbStairs(n) = ClimbStairs(n-1)+ClimbStairs(n-2)。


這個題目的遞推式完全與斐波那契數列吻合。因此可以使用斐波那契數列的快速算法來解此題從而提高效率。只是要區分只有一階樓梯的情況數為1。


有關斐波那契的快速算法，可以看筆者的這篇文章：
http://blog.csdn.net/lan_liang/article/details/40825863




本題的實現代碼：

public class Solution {
    public int ClimbStairs(int n) 
    {
    	return Go(n + 1);
    }


    private int Go(int n)
    {
    	if(n == 1 || n == 2)
    	{
    		return 1;
    	}
    	
    	if(n%2 == 0)
    	{
    		var k = n/2;
    		return Go(k) * (2*Go(k+1) - Go(k));
    	}
    	else
    	{
    		var k = (n-1)/2;
    		return Go(k+1) * Go(k+1) + Go(k) * Go(k);
    	}
    }


}