跳台阶

跳上一个n级的台阶总共有多少种跳法，先后次序不同算不同的结果，限制条件是每次只能跳1级或者2级。

抽象出来的模型是：给定正整数N，有多少种累加方案，不同顺序当做不同方案，限制条件可以是给定的整数$n_0, n_1, ..., n_k$作为可选累加元素.

对于限制条件为只有两种跳法, 即1阶或者2阶的, 问题可以分解为:

  • 假定第一次跳的是1阶，那么就剩下n-1个台阶，剩余跳法是f(n-1);
  • 假定第一次跳的是2阶，则剩下n-2个台阶，剩余跳法是f(n-2)

可以归纳出通用的公式: f(n) = f(n-1) + f(n-2), 只有一阶的时候f(1) = 1, 只有两阶的时候可以有f(2) = 2, 刚好就是斐波那契数列. 所以这个简单的跳台阶问题就是计算斐波那契数列的问题。

反过来思考, 比如对于8个台阶, 有多少种回滚方案? 只有两种: 回滚1个台阶, 就到了7; 回滚2个台阶, 就到了6. 等于说: 假如有f(7)种方案跳到7, 有f(6)种方案跳到6，那么就有f(7) + f(6)种方案到达8

从树结构来理解: 如果节点代表台阶数n对应的跳法f(n), 节点与节点间的枝代表单次可以跳的阶数, 父节点的值就是其所有子节点的值和. 对于只有两种跳法限制问题, 父节点f(n)就只有两个子节点, 分别为f(n-1)和f(n-2).

斐波那契数列

举例：Fibonacci sequence: ${\displaystyle 0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots }$

$$F_0 = 0, F_1 = 1, F_2 = 1, F_n = F_{n-1} + F_{n-2} (n>2) $$

Fibonacci numbers grow almost as fast as the powers of 2.

Recursive solution is exponential algorithm

fib1(n):
    if n = 0:  return 0
    if n = 1:  return 1
    return fib1(n - 1) + fib1(n - 2)

因为每一个fib1()都会生成指数级数量的子分支计算, 所以这个算法复杂度是$O(2^n)$.

但是注意到斐波那契数列公式是$F_n = F_{n-1} + F_{n-2}$, 也就是只要知道n前面两个值, 就能计算出$f_n$. 又因为斐波那契数列天然的是从低往高算, 那么每次迭代只需要用到前两次的值$F_{n-1}, F_{n-2}$, 计算后更新它们即可. 用这个思路来计算斐波那契数列, 复杂度就是$O(n)$.

public int JumpFloor(int target) {
    if (target <= 1) { return target; }
    int n = 2;
    int n0 = 1;
    int n1 = 1;
    int ways = 0;
    while (n <= target) {
        ways = n0 + n1;
        n0 = n1;
        n1 = ways;
        n++;
    }
    return ways;
}

变态跳台阶

变态跳台阶就是是用来更复杂的限制条件, 比如可选单次跳阶数为[1, ... n], 也就是无限制的情况, 也可以按照上面的思路推导.

比如从树结构的考虑, 就变成每个父节点f(n)可以有n个子节点, 就是f(n-1), f(n-2), ..., f(n-n), 所以f(n)就是所有这些子节点的和. f(n-n)也就是f(0)意味着一次跳完所有阶数n, 所以f(0) = 1. 进一步归纳, f(n-2) + ... + f(n-n) = f(n-1), 所以f(n) = f(n-1) + f(n-1), 可以用递归或者动态规划来计算.

当然进一步归纳会发现$f(n) = 2^{n-1}$, 可以用位移来操作:

public int JumpFloorII(int target) {
    int a=1;
    return a << (target - 1);
}

只是要注意int是有范围的.

大变态跳台阶

再举一个更复杂的限制条件, 可选单次跳阶数为$2^0, 2^1, ..., 2^k$, $2^k$要小于n. 那么相应的,

$$f(n) = f(n - 2^0) + f(n - 2^1)... + f(n - 2^k), \quad s.t. \quad 2^k <= n,$$

这样就意味着对于每个f(n), 需要用到的f(k)值数量是不同的, 就不能简单地用固定数量的变量来保留较小值了.

对于不同的f(n), 它们的很多子分支计算是共享的, 比如f(6)和f(5)都用到了f(4). 那么在递归的过程中，只要把每次计算出来的较小的f(k)储存到数组中, 后续其他f(n)要用到f(n - 2^k)时, 直接从内存中取值即可. 初始值取f(0) = f(1) = 1:

public int JumpFloorIII(int target) {
    int[] f = new int[target];
    f[0] = f[1] = 1;
    return jump(f, target);
}

private static int jump(int[] f, int target) {
    if (f[target] == 0) {
        int ways = 0;
        for (int i = 0; (1 << i) <= target; i++) {
            ways += jump(f, target - (1 << i));
        }
        f[target] = ways;
    }
    return f[target];
}

这个代码适用于n <= 1024的情况. 否则要改为循环。