剑指Offer算法题-青蛙跳台阶的问题

题目：一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法？

答题思路

1. 如果只有 1 级台阶，那显然只有一种跳法
2. 如果有 2 级台阶，那么就有 2 种跳法，一种是分 2 次跳。每次跳 1 级，另一种就是一次跳 2 级
3. 如果台阶级数大于 2，设为 n 的话，这时我们把 n 级台阶时的跳法看成 n 的函数，记为$ f(n) $,第一次跳的时候有 2 种不同的选择：一是第一次跳一级，此时跳法的数目等于后面剩下的 n-1 级台阶的跳法数目，即为$ f(n-1) $,二是第一次跳二级，此时跳法的数目等于后面剩下的 n-2 级台阶的跳法数目，即为$ f(n-2) $,因此 n 级台阶的不同跳法的总数为$ f(n) = f(n-1) + f(n-2)$，不难看出就是斐波那契数列

数学函数表示如下

$$
f(x)=\left{
\begin{aligned}
& 0 & n=0 \
& 1 & n=1 \
& 2 & n=2 \
& f(n-1)+f(n-2) & n > 2
\end{aligned}
\right.
$$

code

这里需要注意一下溢出的问题，因为在 swift 里若相加溢出，则会直接 crash，所以这里相加使用了 &+，溢出后返回 nil

func fibonacci(number: UInt64) -> UInt64? {

若把条件修改成一次可以跳一级，也可以跳 2 级…也可以跳上 n 级呢？

思路

1. 如果台阶级数为 n 的话，这时我们把 n 级台阶时的跳法看成 n 的函数，记为$ f(n) $,第一次跳的时候有 n 种不同的选择：若是第一次跳一级，此时跳法的数目等于后面剩下的 n-1 级台阶的跳法数目，即为$ f(n-1) $,若是第一次跳 m(m<n)级，此时跳法的数目等于后面剩下的 n-m 级台阶的跳法数目，即为$ f(n-m) $,若是第一次跳 n 级，此时跳法的数目等于 1.所以 $ f(n) = f(n-1) + f(n-2) + … + f(n-m) + … + f(2) + f(1) + 1 $
2. 因此$ f(n - 1) = f(n-2) + … + f(n-m) + … + f(2) + f(1) + 1 $
3. 两式相减得到 $ f(n) = 2 * f(n-1) $
4. 因此可以得到下面的结果

$$
\begin{aligned}
f(n) &= f(n-1) + f(n-2) + … + f(n-m) + … + f(2) + f(1) + 1 \
&= 1 + f(1) + f(2) + … + f(n-m) + … + f(n-2) + f(n-1) \
&= 1 + f(1) + 2*f(1) + … + 2^{n-m-1} * f(1) + … 2^{n-3} * f(1) + 2^{n-2} * f(1) \
&= 1 + 1 + 21 + … + 2^{n-m-1} + … 2^{n-3} + 2^{n-2} \
&= 2^{n-1}
\end{aligned}
$$

答案

若把条件修改成一次可以跳一级，也可以跳 2 级…也可以跳上 n 级呢，则$ f(n) = 2^{n-1}$