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

长夜漫漫，无心睡眠，不如上 Javaeye 来写帖子吧。

话说前两天有位名唤 mingliangfeng 的朋友（ID 好长 ……），写了一篇好玩的帖子，标题是当当当当 …… 我数数 …… 十四个大字：递归计算向非递归计算转换模板。当时看了帖子和后面的回复就觉得很有意思，存了个念头要就这个题目写一篇相关的东西，显摆一下自己的博学多才。今天不知为何怎么也睡不着，不如就付诸行动，也算造福苍生吧。

嗯，从哪里说起好呢？还是从我的老本行，算法设计技术开始吧。那么下面有请我们的动态规划先生。

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)。程序如下：

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 进去，瞬间你就能看到结果 —— 我们就这样把一个本来需要计算到宇宙末日的问题给解决了。

这种算法设计技巧，就是动态规划。

我相信有些同学一定觉得上面这个例子实在太简单了，你们天才的大脑需要更有挑战性的工作才能满足，所以下面给个稍微复杂点的问题作为思考题，有兴趣的同学可以想一想。这是我面试某公司时遇到的面试题：话说有个魔法字典，其中记录了一些魔力单词（字符串），如果一个句子（也是字符串）可以被完全分解为若干魔力单词的拼接，那么这个句子就是一条咒语。假设我们可以用常数时间查询魔力字典是否包含一个特定的单词，那么现在给你一个句子，让你写一个程序判断这个句子是否一条咒语。用动态规划可以解哦。


嗯嗯，终于困了，待续吧 ……

（下期预告：递归与非递归，函数式语言和逻辑式语言的“远大理想”，更多精彩内容，不要错过！）

你这个例子介绍动态编程挺不合适的呀~~

我查了下书,动态编程划分成四个步骤,你丫根本就没说

坏巫师,标题党~

这篇文章很明显想从动态规划讲到逻辑式语言的自动回溯，直到基于历史的自动回溯。老巫师还没发话完了就给打“新手帖”，真是太不给面子了。
拭目以待吧，我想多数人恐怕只知道迷宫问题，对自动回溯还没什么概念。

楼主凌晨5点多起来发帖子，让我肃然起敬啊
javaeye应该颁给你个劳模奖

Elminster凌晨4点多发帖...是不是看了欧洲杯睡不着，呵呵

我知道动态规划通常有2种方式:
1. 自顶向下 (Top-down)，将问题分解为多个小问题，然后用递归和备忘录(memoization)的方式进行计算，避免相同的小问题重复计算，你这篇文章中计算fib用的就是这种，还是比较容易理解的。

2. 自底向上 (Bottom-up)，我对于这种方式是怎么推导出来的很难理解，不知道E大法师会不会涉及到这一块？

对于大部分动态规划的问题，只要把状态转移方程搞出来了，用递归（自顶向下）还是用递推（自底向上）都不是很难的事情。
相比之下，用递归更符合思维习惯，而且在某些时候可能比递推更快（递归只会计算那些需要计算的子问题，而递推需要把所有的子问题计算出来）；不过递推更容易计算算法的时间复杂度。
不过根据状态转移方程就可以得到算法的时间复杂度为 状态数*决策数*转移费用
空间复杂度一般为 状态数

唔唔, 从回复上看, 动态规划的内容还不能结束 ... ...

此帖得留名。又一轮FP热潮在javaeye展开了。

无论语言级别还是编译器级别或者你自己的程度（函数），保证了表达式f(x).当x相同时，f(x)永远是同一个值，保证f(n)永远只计算一次。好像就ok了吧。

其实命令式语言完全可以搞个什么设计模式啥的出来。

查询魔力字典是否包含一个特定的单词 抽象为 F(x)，那么你能保证对于相同的x，F(x)只运算一次。是这意思吗？

花了很长时间写的，不管有多垃圾，也贴出来了。
测试代码:

package com.abest.test;

import junit.framework.TestCase;

/**
 * User: nihongye
 * Date: 2008-6-18
 * Time: 16:52:58
 */
public class MagicStringTests extends TestCase {
    private MagicString ms;

    protected void setUp() throws Exception {
        ms = new MagicString();
    }

    public void testFind()
    {
        ms.getDictionary().put("你",true);
        ms.getDictionary().put("好",true);
        assertTrue(ms.check("你好"));
        System.out.println(""+ms.format());
    }

    public void testFindComplex()
    {
        initDic(ms);
        assertTrue(ms.check("你好我是谁"));
        System.out.println(""+ms.format());
    }
    public void testFindComplex2()
    {
        initDic(ms);
        assertTrue(ms.check("你好我是谁我是谁你好我是谁我是谁"));
        System.out.println(""+ms.format());
    }

    public void testFindComplex3()
    {
        initDic(ms);
        assertFalse(ms.check("你好我是谁我是谁你好我是谁我是谁三等分你好"));
    }

    private void initDic(MagicString ms) {
        ms.getDictionary().put("你",true);
        ms.getDictionary().put("你好",true);
        ms.getDictionary().put("我",true);
        ms.getDictionary().put("是谁",true);
    }
}

实现:

package com.abest.test;

import java.util.Map;
import java.util.HashMap;

/**
 * User: nihongye
 * Date: 2008-6-18
 * Time: 16:53:41
 */
public class MagicString {
    private Map<String, Boolean> dictionary = new HashMap<String, Boolean>();
    private Word root = new Word(-1,0,null,null);//单词链头，开始位置初始化为-1,作为回溯最终的退出标志
    private String sentence;
    private int start = 0;
    private int next = 1;

    public Map<String, Boolean> getDictionary() {
        return dictionary;
    }

    public boolean check(String sentence) {
        this.sentence = sentence;
        return check();
    }

    private boolean check() {
        if(start >= 0)
        {
            System.out.println("Sentence:"+sentence.substring(start));
        }
        while (start < sentence.length() && start >= 0) {
            boolean findWord = false;
            while (!(findWord = dictionary.containsKey(sentence.substring(start, next))) && next < sentence.length()) {
                next++;
            }
            if (findWord) {
                System.out.println(sentence.substring(start,next)+" start = "+start+" next = "+next);
                new Word(start, next, root.last(), null);//将单词加入单词链中
                start = next;
                next = start + 1;
            }else
            {
                //如果未找到单词，弹出上一个单词,重新从上一个单词起始位置找
                Word last = root.last().detach();
                if (last.start >= 0) {
                    System.out.println("PopWord:"+this.sentence.substring(last.start,last.end));
                }
                this.start = last.start;
                this.next = last.end + 1;
                check();
            }
        }
        return start == sentence.length();
    }


    public String format()
    {
        String result = "";
        Word word = root;
        while((word = word.next) != null)
        {
            result += sentence.substring(word.start,word.end);
        }
        return result;
    }

    class Word {
        int start;
        int end;
        Word prev;
        Word next;

        Word() {
        }

        Word(int start, int end, Word prev, Word next) {
            this.start = start;
            this.end = end;
            this.prev = prev;
            if (prev != null) {
                prev.next = this;
            }
            this.next = next;
        }

        public Word last() {
            Word item = this;
            while (item.next != null) {
                item = item.next;
            }
            return item;
        }

        public Word detach() {
            if(this.prev != null)
            {
                this.prev.next = null;
            }
            this.prev = null;
            return this;
        }
    }
}

　　才发现LZ还出了一个题
　　刚搞定了Project Euler上的40个题，大脑有点兴奋，也来试试吧。
　　首先根据楼主的题目定义两个接口（为了让代码结构清晰点）：

魔法词典的接口

/**
    &#MagicDict
    魔法字典
*/
interface MagicDict{
    /**
      判断word是否为魔法单词
    */
    boolean isMagic(String word);
}

解题的接口

/**
   &#Solver.java
   求解接口
*/
interface Solver{
    /**
       使用dict判断text是否为咒语
    */
    boolean isCharm(String text,MagicDict dict);
}

然后用于生成魔法词典的一个工厂类：

import java.util.Set;
import java.util.HashSet;

/**
   &#MagicDictFactory.java
   将一个Set包装为一个MagicDict,该实现的查询的时间复杂度为O(1)
*/

public class MagicDictFactory {
    public static MagicDict getMagicDict(Set<String> set){
        final Set<String> copy = new HashSet<String>(set);
        return new MagicDict(){
            public boolean isMagic(String word){
                return copy.contains(word);
            }
        };
    }
}