题意
题目：爬楼梯
假如你正在爬楼梯，需要 n 阶才能到达楼梯顶部.
每次你只能爬 1 到 2 阶.请问你可以有多少种方法到达楼梯顶部.
注意：给定的 n 是一个正整数.
题解
算法及复杂度（0 ms）
本题显然是一种全局限制性的路径问题，在一条路径中某个位置只能向后走一步或者两步，也就是说一个位置的上一个位置一定是前一个位置或者前两个位置.
我们还从最后一个位置开始看，如果要到达位置 n ，此时到达 n 的所有路径数应该是到达 n - 1 的所有路径数加上达到 n - 2 的所有路径上（假设此时 n - 1 和 n - 2 均有意义）.也就是问题转化为分别求解到达 n - 1 和 n - 2 的路径数.依次向前递推.
很容易想到，假设起点到达点n的所有路径数表示为状态 dp[n] ，那么有状态转移方程为dp[n] = dp[n - 1] + dp[ n - 2], n >= 2.
显然到达 n - 1 的路径数并不受 n 之后的点的影响，也就是没有后效性.满足使用动态规划求解的要求.
时间复杂度: O(n). 每个点只需要计算一次即可.
代码参见本文件夹下solution.cpp
算法正确性
举个例子
// 输入 n = 5
// 初始化
dp[0] = 1
dp[1] = 1
//继续求解
dp[2] = dp[1] + dp[0] = 2
dp[3] = dp[1] + dp[2] 