青蛙跳台阶变种
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级，但年幼的青蛙不能连续跳 2 级，求年幼青蛙跳上一个 n 级的台阶总共有多少种方法？
递归
假设 n 级台阶有 f(n) 种跳法，则有
\[f(n) = \begin{cases} f(n-1), & \text{if 上一步跳了 2 级} \\ f(n-1)+f(n-2), & \text{if 上一步跳了 1 级} \end{cases}\]当上一步跳的是 1 级时，则当前这一步可跳 1 级或 2 级，否则当前只能跳 1 级，根据公式很容易写出递归代码：
// n：剩余台阶级数
// two：为 1 表示上一步跳了 2 级，为 0 表示上一步跳了1级
int jump(int n, int two) {
if (n <= 1) return n;
if (n == 2) return two ? 1 : 2;
return two ? (jump(n - 1, 0)) : (jump(n - 1, 0) + jump(n - 2, 1));
}
该解法比较容易理解，但显然递归解法效率是很低的，很容易想到利用动态规划来解决它。
动态规划
利用数组保存每次计算得到的值，避免重复计算。
主要思路与递归类似，只不过从递归计算变成了迭代的数组计算。这里给出自底向上的动态规划解法：
int jump(int n) {
vector<vector<int>> v(n + 1, vector<int>(2, 0));
// v[i][0]表示上一跳为 1 级时，剩余 i 级台阶有 v[i][0] 种跳法
// v[i][1]表示上一跳为 2 级时，剩余 i 级台阶有 v[i][1] 种跳法
v[1][0] = 1;
v[1][1] = 1;
if (n >= 2) {
v[2][0] = 2;
v[2][1] = 1;
}
for (int i = 3; i <= n; ++i) {
v[i][0] = v[i - 1][0] + v[i - 2][1];
v[i][1] = v[i - 1][0];
}
return v[n][0];
}
时间复杂度为 O(N)。
组合数学
把问题抽象成简单数学模型，假设有 x 次 2 级跳，y 次 1 级跳，则 x、y 必定满足如下关系式：
\[\begin{cases} 2x + y = n & \text{(1)} \\ x \le y+1 & \text{(2)} \end{cases}\]其中 (1) 式是显然的，而 (2) 式若不满足则必定存在相邻的 2 级跳。
要使 x 个 2 级跳均不相邻，可以使用插空法对所有组合数进行分析。
\[\underbrace{...\quad\underbrace{2\quad2\quad2\quad2}_{x 个 2}\quad...}_{x+1 个空位}\]其中由于不能有相邻的 2，因此先给中间 $x-1$ 个空位插入 $x-1$ 个 1，然后将剩下 $n-2x-(x-1)=n-3x+1$ 个 1 任意分配到 $x+1$ 个空位。
问题就转化为了经典的 $a$ 个球放入 $b$ 个盒子的问题，$a$ 个球相同，$b$ 个盒子不同，盒子可以为空，组合数为 $C_{a+b-1}^{a-1}$。在本问题中 $a=n-3x+1$, $b=x+1$。代码如下：
// 计算 C(a, b)
int cal_c(int a, int b) {
if (a == 0)
return 0;
if (b == 0) return 1;
int a_fac = 1, b_fac = 1;
for (int i = a; i > a - b; --i)
a_fac *= i;
for (int i = 1; i <= b; ++i)
b_fac *= i;
return a_fac / b_fac;
}
int jump(int n) {
if (n <= 2) return n;
int total = 0;
int a, b;
for (int x = 0; x <= (n + 1) / 3; ++x) {
a = n - 3 * x + 1;
b = x + 1;
total += cal_c(a + b - 1, b - 1);
}
return total;
}
时间复杂度 O(N)。