爬楼梯及其进阶

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
LeetCode链接：https://leetcode.cn/problems/climbing-stairs/description/

爬楼梯

递归

    爬 n 层楼梯的所有方式 f(n) 可以表示为 f(n) = f(n-1) + f(n-2)。因为一次只能爬一层或者两层，因此到第 n 层前仅可能位于第 n-1 层或第 n-2 层。又可将 n-1、n-2 代入 n ，而最底层为 n = 1、 n = 2，即 f(1) = 1、f(2) = 2。可得：

#define MAX_LENGTH = 51;
vector<int> memo(MAX_LENGTH, -1);
int stair(int n) {if (n == 1)return 1;if (n == 2)return 2;if (-1 == memo[n])memo[n] = stair(n - 1) + stair(n - 2);return memo[n];// return stair[n-1] + stair[n-2];
}
class Solution {
public:int climbStairs(int n) { return stair(n); }
};

提交结果：

动态规划

     占位

爬楼梯进阶

由于体力有限，一次爬两层后接下来两次每次只能爬一层，你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 6
输出：7
解释：第七项中，一次爬两阶后，后续两次只能为一阶。
1. 1 阶 + 1 阶 + 1 阶 + 1 阶 + 1 阶 + 1 阶
2. 2 阶 + 1 阶 + 1 阶 + 1 阶 + 1 阶
3. 1 阶 + 2 阶 + 1 阶 + 1 阶 + 1 阶
4. 1 阶 + 1 阶 + 2 阶 + 1 阶 + 1 阶
5. 1 阶 + 1 阶 + 1 阶 + 2 阶 + 1 阶
6. 1 阶 + 1 阶 + 1 阶 + 1 阶 + 2 阶
7. 2 阶 + 1 阶 + 1 阶 + 2 阶

思路

     在该问题中，当前可爬台阶数受到上一次执行结果的影响，因此需要考虑上一层的状态，为此我的思路是引入额外的变量进行标识。变量 flag 表示在经过几次爬升一阶后可以进行选择爬升阶梯的数量，当 flag > 0 时，每次只能爬一阶，当 flag = 0 时，可以选择下次爬一阶或者爬两阶，如果选择爬两阶需要把 flag 置为2，在起始状态下 flag 的值为0。

long long stair(int n, int flag = 0) {long long v;if (n <= 0)return 0;if (1 == n)return 1;if (2 == n) {if (0 == flag)return 2;elsereturn 1;}if (flag > 0) {v = stair(n - 1, flag - 1);}else {v = stair(n - 1, 0) + stair(n - 2, 2);}return v;
}

算法的运行结果为：
爬升5阶，有：5种方法
爬升6阶，有：7种方法
爬升7阶，有：10种方法
爬升8阶，有：14种方法
爬升9阶，有：19种方法
爬升10阶，有：26种方法
爬升11阶，有：36种方法
爬升12阶，有：50种方法
爬升13阶，有：69种方法
爬升14阶，有：95种方法
爬升15阶，有：131种方法

思考

     怎么使用记忆进行存储，从而避免不必要的计算资源浪费。