动态规划，递归与非递归，FP 之野望，描述与计算

1. 动态规划 动态规划这四个大字在算法设计这一块算是鼎鼎有名。它不是什么高深的东西，就是算法设计里面最基础的法门，少林长拳是也。基本上判断一个人是不是真的学过算法，考考动态规划就知道了。有趣的是，这动态规划偏偏就是和递归较劲的，而这个最简单的例子就是著名的肥婆拉车 …… 呃，斐波纳契（Fibonacci）数列了。 这个数列是这么定义的（知道的同学请跳过这一段）：记 fib(n) 为斐波纳契数列的第 n 个元素，则 fib(0) = 0, fib(1) = 1, 对于所有的 n > 1 ，有 fib(n) = fib(n-1) + fib(n-2) 。巧得很，那位 ID 很长的 M 朋友（以后直接用 M 简称了，相信 007 不会介意），要计算的函数差不多也是这么个形式，所以下面的讨论，基本上可以一字不差的套用过去。 要计算这个函数，最直截了当的实现就是用递归了：

int fib(int n)
{
    // 不要和我扯什么函数参数检查之类，喜欢抠这些的请去隔壁的对日外包培训班

    if (n == 0)        return 0;
    else if (n == 1)   return 1;
    else               return fib(n-1) + fib(n-2);
}

这个实现基本上就是照抄数列的定义，任何智商正常的程序员都能写出来、看得懂。但是如果说起运行效率，那完全可以用一坨有机肥料来形容。嗯嗯，当然了，搞算法的人不可以信口开河，光说人家像有机肥料是不行的，你得严格证明这一点，那么现在就让我们来简单分析一下：记 fib(n) 运行所需的时间为 T(n)，显然 T(0) 和 T(1) 是常数，而对于所有的 n > 1， T(n) = T(n-1) + T(n-2) + 某个常数。Javaeye 不支持 latex，数学公式展不开，我们就取个最粗略的分析。显然，对于所有的 n > 1，T(n) 是单调增加的，满足 T(n) > T(n-1) > T(n-2) ... （有兴趣的同学可以数学归纳一把确证一下），因此 T(n) = T(n-1) + T(n-2) + 某个常数 > 2*T(n-2) ，所以 T(n) = Ω(2^{n/2})。通俗点说，n 每增大 2，T(n) 至少要翻一倍，如果 n = 256 ，那么这段程序多半是没有希望在宇宙毁灭之前运行完了。 这见鬼的肥婆 …… 斐波纳契数列真的那么难算么？当然不是，上面那段程序的问题在于包含了太多的重复计算。让我们看下面这张图（此图无耻地盗链自 SICP 的公开电子书）： 看图，这是上面那个递归程序计算 fib(5) 的过程。一眼可以看出，这里面冗余无数，比如fib(5) 那棵计算 fib(3) 的右子树和 fib(4) 的左子树完全是相同的。这种冗余计算耗费了几乎全部的程序运行时间，从而使得这个程序的运行效率散发出有机肥料的气味。只要消除这些冗余，就能让程序运行速度快起来。 那么具体如何着手呢？看看那个递归式子，fib(n) = fib(n-1) + fib(n-2) ，从本质上来讲，这个式子真正告诉我们的是这样一件事：计算 fib(n) 这个任务，可以分解为计算 fib(n-1) 和计算 fib(n-2) 这两个新任务，而计算 fib(n-1) 和 fib(n-2) 这两个新任务，也可以继续通过这个递归式子分解下去，直到我们遇到 fib(0) 和 fib(1) 。算一算，我们一共可能遇到几个不同任务？fib(0) 到 fib(n) 一共 n + 1 个，而且我们有了 fib(0) 和 fib(1) ，就能算出 fib(2)，有了 fib(1) 和 fib(2) 就能算出 fib(3) …… 以此类推，我们可以照着这个顺序把这区区 n + 1 个计算任务全都给完成了，从而也就得到了 fib(n)。程序如下：

Java代码

int fib(int n)
{
    int[] fibs = new int[max(2, n+1)];  // 保存 n + 1 个计算任务结果的数组
                                        // PS：其实没必要保留这么多空间，这里是为了说明起来更清楚
    fibs[0] = 0;                        // 第 1 个计算任务
    fibs[1] = 1;                        // 第 2 个计算任务
    for (int i=2; i<=n; ++i)            // 第 2 到 n 个计算任务
    {
        fibs[i] = fibs[i-1] + fibs[i-2];
    }
    return fibs[n];
}

这个程序的时间复杂度是 O(n) ，也就是线性时间（看不出来的回去重修数据结构），传个 n = 256 进去，瞬间你就能看到结果 —— 我们就这样把一个本来需要计算到宇宙末日的问题给解决了。 这种算法设计技巧，就是动态规划。 我相信有些同学一定觉得上面这个例子实在太简单了，你们天才的大脑需要更有挑战性的工作才能满足，所以下面给个稍微复杂点的问题作为思考题，有兴趣的同学可以想一想。这是我面试某公司时遇到的面试题：话说有个魔法字典，其中记录了一些魔力单词（字符串），如果一个句子（也是字符串）可以被完全分解为若干魔力单词的拼接，那么这个句子就是一条咒语。假设我们可以用常数时间查询魔力字典是否包含一个特定的单词，那么现在给你一个句子，让你写一个程序判断这个句子是否一条咒语。用动态规划可以解哦。