问题：
假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法爬到楼顶部？
分析：
其实就是斐波那契数列的应用，递推公式为： f(i) = f(i-1) + f(i-2)
可以直观的使用递归，但是时间复杂度与规模n成指数关系，下面介绍动态规划解法。
代码：
int climbStairs(int n) {
// 开一个长度为 n+1 的数组记录状态，也称‘打表’
if(n==0){
return 1;
}
else if(n==1){
return 1;
}
int dp[n+1] ;
dp[0]=dp[1]=1;
for(int i=2;i<=n;i++){
dp[i] = dp[i-1]+dp[i-2];
}
return dp[n];
}
事实上，由于i 只和前两项有关,我们还可以省下O(n)的空间复杂度，但时间复杂度并未改变
int climbStairs(int n) {
// write your code here
if(n==0){
return 1;
}
else if(n==1){
return 1;
}
int m1=1,m2=1;
for(int i=2;i<=n;i++){
m2 = m1+m2;
m1 = m2-m1;
}
return m2;
}
