题目描述：
初阶：有n层的台阶，一开始你站在第0层，每次可以爬两层或者一层。请问爬到第n层有多少种不同的方法？
进阶：如果每次可以爬两层，和倒退一层，同一个位置不能重复走，请问爬到第n层有多少种不同的方法？
解题思路：
初阶：一维动态规划。爬楼梯数目其实是一个斐波拉契数列。
初值：f[0] = 1, f[1] = 1。//最开始没有爬和第一层的方法数目为1.
输出：f[n] 爬到第n层的方法数目。
实现方法两种：迭代法、递归法
递归法：时间复杂度：O(n) ，空间复杂度：O(n)
迭代法：时间复杂度：O(n)，空间复杂度：O(1)
//递归法class Solution {public:/*** @param n: An integer* @return: An integer*/int climbStairs(int n) {// write your code herevector<int> ans(n+1);ans[0] = 1;ans[1] = 1;for(int i=2; i<=n; i++)ans[i] = ans[i-1] + ans[i-2];return ans[n];}};//迭代法class Solution {public:/*** @param n: An integer* @return: An integer*/int climbStairs(int n) {// write your code hereint prev = 0;int cur = 1;for(int i=1; i<=n; i++){int tmp = cur;cur += prev;prev = tmp;}return cur;}};
进阶：参考这里
主要是倒退一层，这个地方可能会违背动态规划无后效性的原则。 那么我们要怎么转化呢？由条件：同一个位置不能重复走。我们可以知道如果要退步的话，不能退两层以上，因为用两步退两层再一步前进两层，那就会走相同的位置。所以我们最多只能退后一步。
那么题目的条件就可以转换两种情况，，
a.跳两层（前进两层）。b.退一层跳两层 （前进一层）。1.State:
f[i][0] 表示最后一步是跳两层情况下爬到第i层的方法数目。
f[i][1] 表示最后是一步是退一层跳两层的情况下爬到第i层的方法数目。
2. Function:
f[i+1][1] = f[i][0] 最后一步是退一层跳两层的情况下爬到第i+1层的方法数目等于 从第i层情况a的数目跳两层退一层。
这里不能考虑第i层的情况b的方法数，因为第i层情况b的数目是从第i+1层退一步得到的。
f[i+2][0] = f[i][0]+f[i][1] 最后一步是退一层跳两层的情况下爬到第i+2层的方法数目等于 第i层所有情况跳两层。
3. Intialize:
f[0][0]=1初始化最开始没有爬的方法数目为1.
4. Answer:
f[n][0]+f[n][1] 爬到第n层a、b两种不同的方法的总和
如果你希望成功，以恒心为良友，以经验为参谋，以小心为兄弟，以希望为哨兵。
