题目
思路
这道题我们可以使用动态规划。
用f(x)代表爬到第x级台阶的方案数，爬到x级台阶只有两种方法，一种是从前一层（x-1）爬一层台阶或从前两层（x-2）爬两级台阶即可。
f(x) = f(x-1)+f(x-2)
它意味着到x层台阶的方案数等于到x-1层和x-2层之和，很好理解。因为每次只能爬一个或两个台阶，所以f(x)只能从f(x-1)和f(x-2)转移来，因为要求方案总数，所以就对两边求和。
解题过程
首先列出特殊情况：0，1，2
接着定义一个数组f
f[0]代表一层台阶的方案数
f[1]代表两层台阶的方案数
i从2开始循环，说明从第三层台阶开始算，爬到第三层的方案数等于爬到第一层与爬到第二层方案数的总和。最后f[n-1]即为爬到最后一层台阶的方案数
代码
class Solution {
public:int climbStairs(int n) {if(n == 0) return 0;if(n == 1) return 1;if(n == 2) return 2;//从三楼开始，只有两种上楼方式，从前一层爬一楼或者从前两层爬两楼//可以推出f(n) = f(n-1)+f(n-2)vector<int> f(n);f[0] = 1;f[1] = 2;for(int i=2;i<n;i++){f[i] = f[i-1] + f[i-2];}return f[n-1];}
};优化
这个题的时间复杂度是O（N）,空间复杂度也是O（N），因为创建了一个空间为n的数组。
因为f(x)只与f(x-1)和f(x-2)有关，所以我们可以用p代表f[0],q代表f[1]，r代表f[i]。
利用滚动数组的思想将空间复杂度降为1。
不断改变p,q,r的值将数组向前推移
int p = 1;int q = 2;int r = 0;for(int i=2;i<n;i++){r = p + q;p = q;q = r;}return r;
