题目描述：爬n阶的楼梯，可以每次爬一阶或者两阶，求不同的方式数量
思路：
这个题目是一个计算n层阶梯情况下，走到顶端的路径种数（要求每次只能上1层或者2层阶梯）。
这是一个动态规划的题目： n = 1 时 ways = 1； n = 2 时 ways = 2； n = 3 时 ways = 3； … n = k 时 ways = ways[k-1] + ways[k-2]；
如有需要，请访问我的Github获取包含测试程序的C++源码。
class Solution { public: int climbStairs(int n) { //当台阶数等于1时，方式为1 if(n == 1) { return 1; } //当台阶数等于2时，方式为2（1+1或者2） if(n == 2) { return 2; } //申请空间，从0到n个台阶，一定是n+1个空间！！！ int *ways = new int[n + 1]; ways[0] = 0; ways[1] = 1; ways[2] = 2; for(int i = 3; i <= n; i++ ) { //递推公式 ways[i] = ways[i - 1] + ways[i - 2]; } return ways[n]; delete []ways; ways = NULL; } };20180801更新：使用vector存储结果，省去申请和释放空间的麻烦
class Solution { public: int climbStairs(int n) { //当台阶数等于1时，方式为1 if(n == 1) { return 1; } //当台阶数等于2时，方式为2（1+1或者2） if(n == 2) { return 2; } vector<int> v(n); v[0] = 1; v[1] = 2; for(int i = 2; i < n; i++ ) { //递推公式 v[i] = v[i - 1] + v[i - 2]; } return v.back(); } };