/****************************
   Name: stairs climbing 爬楼梯问题
   Date: 01/27/2016
   Author: Hualin Li
   Description: This is the stairs climbing question in the C++. 第一题选择这道也许是天意吧...
   做题感想：该题目有两种经典解法。但无论是第一种（递归法）或者是第二种（动态编程法即dp--呵呵，dp哦）
   大家只要记住一点 n（i）=n (i-1)+n(i-2）这个斐波那契数列的特性，一切问题就迎刃而解。顺便说一句，
   该题目在电影《少年班》中也出现过，想当年自己也和少年班一起上过概率论。但时过境迁，当年一起在课堂上听课
   的同学们恐怕大多都成为了各个行业的翘楚。借用非主流相声演员郭公德刚的说法：但行好事，莫问前程吧。
   
*****************************/
public int stairRecursive(int n)
{
   if(n==0||n==1||n==2)
	   return n;
   else 
	   return stairsRecursive(n-1)+stairsRecursive(n-2);
}

以上解法为递归解法，编译通过且答案正确。但是leetcode运行超时。如果大家暂时不能理解该解法，不妨倒过来思考：
如果你要走1000级楼梯，你的最后一步也许是从第999级往上走一级，或者从第998级一次走两级。于是n（1000)=n(999)+n(998).
  

public int stairsDP(int n)
{
	
	if(n==0||n==1||n==2)
		return n;
	int ans[n];
	ans[0]=0;
	ans[1]=1;
	ans[2]=2;
	//DP begin from here
	if(n>=3)
	{
		for(int i=3;i<=n;i++)
		{ans[i]=ans[i-1]+ans[i-2];}
	return ans[n];
	}
}
以上解法为DP解法。利用斐波那契数列的定义，答案不言自明，该解法通过了leetcode的运行测试。