leetcode链接 

70. 爬楼梯 - 爬楼梯 - 力扣（LeetCode）

爬楼梯问题的本质是斐波那契数。这个题可以用递归来解决：

int climbStairs(int n)
{if(n==1)return 1;if(n==2)return 2;else return climbStairs(n-1)+climbStairs(n-2);
}

但是，这种算法时间复杂度是O(N^2)，不能AC。

所以不能用存粹递归了。

那就需要动态规划了。可以使用滚动数组。

即，定义一个数组，初始化为0。

然后给第二个元素赋值1，给第三个元素赋值2。由于先前已经将所有元素初始化为0，所以第一个元素就是0。

首先考虑边界，当n=1时，返回值为1，当n=2时，返回值为2。

当n>=3时，进入循环，然后每次stairs[i]的值是相邻前两项的和。

退出循环后最终返回stairs[n]。

int climbStairs(int n)
{int stairs[50]={0};stairs[1]=1;stairs[2]=2;for(int i=3;i<=n;i++){stairs[i]=stairs[i-1]+stairs[i-2];}return stairs[n];
}

这样下来时间时间复杂度就成了O(N)。