主流的编程语言中，表示出现错误的手段不外乎两种：

• 函数调用返回错误码
• 函数调用抛出异常

C语言就属于前者，它的fopen(3)函数在成功打开文件时返回一个FILE指针，失败时返回NULL，并将错误代码写入全局变量errno；Ruby语言属于后者，它的File.open方法在找不到文件时抛出ENOENT的异常，在File.open之外包裹一层begin…rescue…end即可捕捉其抛出的异常。

Common Lisp的错误机制叫做状况系统（Condition System），与异常机制相似，可以实现抛出异常（使用函数error）和捕捉异常（使用宏handler-case）。但与其它语言的异常机制不同的地方在于，状况系统有一种名为RESTART的特性，能够由使用者、或者由代码决定是否要、以及如何从错误中恢复过来。听起来很别致也很诡异，不妨继续往下看。

假设我有一个Web框架，它提供了将日志记录到文件中的功能。这个功能需要先调用名为init-logger的函数进行初始化，该函数实现如下

1
2
3
4
5

(defun init-logger ()
  (with-open-file (s "/tmp/log/web.log"
                     :direction :output
                     :if-exists :supersede)
    (format s "Logger module starting...")))

这个函数被框架的初始化代码所调用，如下

1
2
3
4
5
6
7

(defun init-framework ()
  (format t "Framework starting...~%")
  (init-plugin))

(defun init-plugin ()
  (format t "Plugins starting...~%")
  (init-logger))

而框架的初始化代码则由应用的初始化代码所调用，如下

1
2
3

(defun init-app ()
  (format t "Application starting...~%")
  (init-framework))

如果在目录/tmp/log不存在时调用init-app函数，我将会收到一个错误，说明其无法找到/tmp/log/web.log这个文件。为了避免错误打断了应用的正常启动流程，可以让init-app函数负责创建这个用于存放日志文件的目录。将init-app函数改写为如下形式

1
2
3
4

(defun init-app ()
  (format t "Application starting...~%")
  (ensure-directories-exist "/tmp/log/")
  (init-framework))

尽管这种做法确实可行，但它导致应用层的代码（init-app函数）必须了解位于底层的日志模块的实现细节。直觉告诉我这样子是不对的，框架的事情应该由框架本身提供方案来解决。借助Common Lisp的restart功能，框架确实可以对外提供一种解决方案。

首先需要主动检测用于存放日志文件的目录是否存在。借助UIOP这个包可以写出如下代码

1
2
3
4
5
6
7
8

(defun init-logger ()
  (let ((dir "/tmp/log/"))
    (unless (uiop:directory-exists-p dir)
      (error 'file-error :pathname dir))
    (with-open-file (s (format nil "~Aweb.log" dir)
                       :direction :output
                       :if-exists :supersede)
      (format s "Logger module starting..."))))

接着，init-logger需要主动为调用者提供目录不存在的问题的解决方案，一种办法就是当这个目录不存在时，可以由调用者选择是否创建。使用Common Lisp的restart-case宏，我将init-logger改写为如下形式

1
2
3
4
5
6
7
8
9
10
11
12
13

(defun init-logger ()
  (let ((dir "/tmp/log/"))
    (restart-case
        (unless (uiop:directory-exists-p dir)
          (error 'file-error :pathname dir))
      (create-log-directory ()
        :report (lambda (stream)
                  (format stream "Create the directory ~A" dir))
        (ensure-directories-exist dir)))
    (with-open-file (s (format nil "~Aweb.log" dir)
                       :direction :output
                       :if-exists :supersede)
      (format s "Logger module starting..."))))

此时如果调用第一版的init-app函数，那么init-logger仍将抛出异常（类型为file-error与之前一样）并将我带入到SBCL（我用的是SBCL）的调试器中，但看到的内容会稍有不同

1
2
3
4
5
6
7
8

error on file "/tmp/log"
   [Condition of type FILE-ERROR]

Restarts:
 0: [CREATE-LOG-DIRECTORY] Create the directory /tmp/log ;; <- 新增了这一行
 1: [RETRY] Retry SLIME REPL evaluation request.
 2: [*ABORT] Return to SLIME's top level.
 3: [ABORT] abort thread (#<THREAD "new-repl-thread" RUNNING {1001F958A3}>)

在Restarts中新增了名为create-log-directory的一项，这正是在init-logger中通过restart-case定义的新的”恢复措施“。我输入0触发这个restart，Common Lisp会回到它被定义的restart-case宏相应的子句中执行其中的表达式，也就是调用CL:ENSURE-DIRECTORY-EXIST函数创建/tmp/log。

如果总是希望执行CREATE-LOG-DIRECTORY这个选项来创建存放日志文件的目录，可以直接在代码中指定，只需要配合使用Common Lisp的handler-bind和invoke-restart函数即可，最终init-app函数的实现如下

1
2
3
4
5
6
7

(defun init-app ()
  (format t "Application starting...~%")
  (handler-bind
      ((file-error #'(lambda (c)
                       (declare (ignorable c))
                       (invoke-restart 'create-log-directory))))
    (init-framework)))

在战舰少女贴吧里，偶尔能看到的一个说法叫做“这活动我用脚打都能过”，意思是活动关卡很容易（实际上有时候并非真的那么简单，仅仅是调侃）。在安装mysql这件事情上，也有用脚安装和用手安装两种。

典型的用脚安装就是使用系统的包管理器。例如在我的LinuxMint系统中，在shell中键入下列命令就可以装上mysql

1

sudo apt-get install mysql-server

遗憾的是，包管理器并不是任何时候都可用的。举个例子：以前在UC，研发团队是可以申请到一些机器用于分配给开发人员使用的，但如果要在上面使用数据库，那么多半需要开发人员自己动手部署。此外，只要掌握了手动部署单个mysql实例的方法，就可以轻松地在一台机器上部署多个mysql实例了，而这正是我最近需要完成的一个任务。为了方便自己很久之后查阅，也为了帮到其他有此类需求的程序员，我写了这篇手动安装的指南。

初始化数据库

安装mysql的第一步，是创建数据库运行所需要的一系列文件。在5.7.6版本之前的mysql中，这个过程是由mysql_install_db这个脚本完成的。在5.7.6的发行版中，这个功能被集成到了mysqld中，下面的操作也是基于mysqld实现的。mysqld提供了执行用于初始化的命令行选项：

• –initialize
• –initialize-insecure

–initialize-insecure会为数据库的root账户设置空的密码，方便稍后登录，因此将选用这一个初始化的方法。

为了初始化数据库，还需要指定mysql的安装目录和存放数据文件的目录。安装目录即mysql的二进制安装包解压缩后生成的目录，而存放数据文件的目录则可以自由选择。这两个路径分别传递给mysqld的–basedir和–datadir参数。为了方便起见，也为了避免mysqld启动后读取了已存在的mysql配置文件造成干扰，我将这两个参数写到了配置文件中。在我的机器上配置文件路径是~/local/mysql/my.cnf，内容如下

1
2
3

[mysqld]
basedir = /home/liutos/local/mysql
datadir = /home/liutos/data/mysql/data

需要注意的是，根据官方文档的说明，datadir所设置的目录，必须为一个尚不存在的目录或者是一个空目录。在我的系统中，/home/liutos/data/mysql/data是一个尚未创建的目录。

现在可以进行初始化了。因为在我的系统上解压缩后的目录为~/local/mysql，因此在shell中执行的命令为

1
2

cd ~/local/mysql/
./bin/mysqld --defaults-file=/home/liutos/local/mysql/my.cnf --initialize-insecure --user=`whoami`

启动数据库服务

完成初始化后就可以启动mysqld了。启动的命令为

1

./bin/mysqld_safe --defaults-file=/home/liutos/local/mysql/my.cnf --user=`whoami` > /dev/null 2>&1 &

由于在我的系统中，已经使用包管理器安装了mysql服务并且正在监听着3306端口，为此必须修改即将启动的mysqld进程所监听的端口。监听的端口号可以通过配置文件来指定，修改后的配置文件如下

1
2
3
4

[mysqld]
basedir = /home/liutos/local/mysql
datadir = /home/liutos/data/mysql/data
port = 3307 # 新增该行

现在可以执行刚才的启动命令了。成功启动后，使用netstat -apn | grep '3307'应当可以看到类似下文的输出

1

tcp6       0      0 :::3307                 :::*                    LISTEN      30898/mysqld

登录数据库

一番波折，终于可以登录了。因为当初是使用–initialize-insecure执行初始化的，root账户没有登录密码，因此在shell中键入下列命令登录

1

mysql -u root --skip-password -h 127.0.0.1 -P 3307

登录后建议为root账户设置登录密码。例如，我要给root账户设置密码为1234567，就执行下列SQL语句

1

ALTER USER 'root'@'localhost' IDENTIFIED BY '1234567';

UNIX socket配置

按照上述步骤启动后，mysqld会在系统的/tmp目录下创建一个mysql.sock文件。此时如果再按照上述步骤是无法启动另一个mysql实例的，因此每一个mysqld必须使用单独的.sock文件。这可以通过配置文件来实现，在我的系统上的配置如下

1
2
3
4
5

[mysqld]
basedir = /home/liutos/local/mysql
datadir = /home/liutos/data/mysql/data
port = 3307
socket = /home/liutos/local/mysql/mysql.sock # 新增该行

题外话

大一的时候为了装13就自己去图书馆借了很多讲解和CS有关却又还没有教或者不会教的内容的书来看，其中就有数据结构那一类的。不过我已经忘记了当时去图书馆借到的是什么样子的书了，只知道书的封面是蓝色的（要是有空的话去图书馆找找就可以知道了=。=）。不过说到数据结构方面的书，在国内大部分和计算机或者信息技术沾边的专业的学生中，比较广为人知的应该既不是《算法导论》，也不是《算法概论》，而是编者为严蔚敏的那本《数据结构C语言描述》吧。我也有幸看过，并且印象中那时候觉得那本教材还是不错的。只不过现在道行稍微有点高了，就开始有点鄙视当初习得技能的恩师了——哦，有种过河拆桥的感觉。

百度面试题

第一次去百度面试时，面试官看起来和蔼可亲，同样给出的问题也很和蔼可亲。当时的问题有三道，第一道是让我随意写一个二叉树的遍历的代码，我挑了个深度优先搜索来写，因为我觉得这货算得上是最容易写的代码之一了。然后面试官就让我用广度优先搜索再写一遍，我就再写了一次。说真的，队列那一部分的处理还真是让人头大，尤其是我居然稀里糊涂地把队列的处理和栈的处理混淆在一起了，结果代码看起来也是稀里糊涂的。要不是面试官大慈大悲耐心地和我商量着来修改，我可能就没有遇到第三题的机会了。不过终究第二题还是安全过关了，之后就是第三题了：给广度优先搜索增加一个返回所找到的关键字在二叉树的哪一层的功能。

老实说，听到题目的当即我就想到了一种最最最简单的办法，就是修改二叉树的定义，给它增加一个数据字段来存储每一个节点究竟位于第几层就可以了嘛，唉真是简单得无趣啊=。=不过面试官说不允许这样做，那好，我再换一种办法，就是增加一个新的队列来存储每一个进入队列的节点究竟是位于哪一层的。因为一开始肯定是从第一层开始的，所以只要中间的每一个节点都不要漏掉，那么根据父节点的层数就可以推知直接的子节点的层数，那么在将每一个节点入队列的时候都有办法知道它们是在哪一层的。嗯，这个办法也很好，不过面试官也不允许增加新的队列，呃。。你这不是存心刁难我么！还好，把队列的版本稍微修改一下就可以去掉队列了，不过要增加广度优先搜索的实现函数的参数。

第三个版本

首先要明确这个函数的参数与返回值究竟是怎样的。因为当时这个功能是用C语言来实现的，所以只允许函数调用有一个返回值。在一开始写的两个版本中函数的返回值是所找到的二叉树中的节点，所以在第三个版本中也依然返回所查找到的节点或者是在找不到的时候返回C语言中的空——NULL。那么这样一来节点所对应的深度的信息只能通过下面的两种方法来返回了：

• 全局变量
• 传出参数

我选择了第二种，因此查找功能需要增加一个传出参数depth，它的类型声明是int *。因此查找功能的入口函数的整体类型声明为：

TreeNode dfs_search_tree(Tree tree, char target, int *depth)

（我觉得标识符取得还不错，不用解释了吧→_→）那么dfs_search_tree这个函数要如何实现具体的功能呢？现在我们是为了要在队列的版本上进行修改来实现查找功能的，那么原本需要使用队列来存储的深度信息现在应该交给函数的参数来存储，但是这个参数不能添加到入口函数中，因此我们需要一个辅助函数，就叫做dfs_search_tree_aux函数好了，它至少需要上面的函数所拥有的三个参数，并且还需要一个用来传递而不是用来返回的深度的信息，不妨声明为int *nd。

试想一下，如果我们在处理第i层的一个节点，那么显然可以知道它的左右子树的根结点如果存在，必定会位于第i+1层，因此在广度优先搜索的函数递归调用的时候，nd参数的传递是以加一的形式进行的，即遍历子树的时候nd必定要比测试当前节点的时候加一。不过实际上这样子是不可行的，因为我们不是在测试了父节点之后就立即递归调用函数来测试两个子节点，在测试父节点的时候，只是把两个子节点给放进了队列罢了，因此没有办法通过简单地直接加一的方法来传递深度参数。我们需要的信息是，现在这个节点和上一个节点到底是不是在同一层。

确定是否在同一层的一个办法，是知道每一层的节点的数目。例如第一层显然只能有一个节点，因此当测试了第一个节点后就可以知道第一层已经测试完了，那么接下来的函数调用的nd参数的值就至少应该增加一，并且应该把表示一层的节点个数的参数设置为第二层的对应值。第二层的节点个数可以利用遍历第一层的时候来得到。例如对于第i层的节点，如果每一个节点都有两个子节点，那么第i+1层的节点数目就是第i层的两倍，对于其它情况也可以很简单地推算出来。因此，我们需要额外的两个参数current_count和next_count，来分别存储当前层剩下的节点数目以及下一层目前所探测到的节点数目。现在，我们可以写出辅助函数的原型了：

TreeNode dfs_search_tree_aux(char target, int depth, int *nd, Queue queue, int current_count, int next_count)

其中没有和dfs_search_tree一样的tree参数，因为在广度优先搜索中，树的节点是存储在队列queue中的。dfs_search_tree_aux这个函数的逻辑是这样子的：

1. 先看看队列是否为空。如果是就说明节点都已经测试完了，仍然没有找到目标节点，所以返回NULL；
2. 从队列中取出最早进入的节点。
3. 既然已经开始测试新的节点，那么当前层的剩余节点数就少了一个，因此current_count要自减一；
4. 测试节点的关键字。如果是一致的就先设置传出参数nd为depth，然后返回对应节点的指针；
5. 如果测试失败，那么就说明函数需要继续递归调用下去了。这时候需要先决定current_count和next_count的值。
6. 如果current_count为0，也就是说这一层没有节点剩下了，那么就让depth加一，把当前的节点数目（current_count）设置为下一层的节点数目（next_count），然后下一层的节点数目重新归零。
7. 接下来，测试左子树是否为空。如果非空，就把当前节点的左子树根结点入队，并给next_count加一。同样的，右子树也是类似的处理办法。
8. 最后，递归调用辅助函数本身。

最后给出代码链接好了：https://github.com/Liutos/CLab/blob/master/binary_tree/prototype.c。

话题由来

参加了不少IT公司的笔试，有些题目遇到的次数还是比较多的，例如给一系列字符和一个空栈，询问你选项中的哪一个是不可能出现的出栈顺序这样的问题。另外一道题目，就是我这里要拿来讲的，不过我讲的和题目本身不直接相关，只是恰好和题目所要完成的任务有重合罢了。这道题目就是“给出一颗二叉树的先序遍历和中序遍历的输出结果，请给出这个二叉树的后序遍历的输出结果”。

这道题目其实非常简单，尽管我一开始遇到的时候仍然是手足无措的（谁没有年少无知过呢对不），不过一两次之后就轻车熟路了，知道了这样的题目的行之有效的解法。举个例子，先序的序列和中序的序列分别是”abfce”和”bface”，那么这棵二叉树就是这样子的

可以知道，后序遍历的输出结果为”fbeca”。怎么得到这棵二叉树呢？其实很简单，首先根据先序遍历的定义，所以在先序遍历结果中的第一个元素一定是整棵二叉树的根结点，也就是a，那么根据中序遍历的定义，在a左边出现的序列就是左子树的中序遍历结果，在a的右边的就是右子树的中序遍历结果，它们分别是”bf”和”ce”。并且可以知道，在先序遍历中与它们对应的片段应该也是”bf”和”ce”。在对”bf”做同样的处理，就可以知道b是根结点，而左子树为空且右子树为单节点f，另一棵子树的根结点为c且左子树为空，右子树为单节点e。

那么，怎么用程序来自动化呢？

C语言的递归版本

以文字来描述根据先序和中序来构造二叉树的算法还是很好理解的。为了描述方便，取几个名字。把先序遍历的结果叫做preseq，中序遍历的输出结果叫做inseq，并且把它们当作C语言中的数组那样来取出元素（例如preseq[0]表示第一个元素），再给它们一个方便取出片段的语法糖，例如preseq[0..2]表示取出下标从0到2的三个元素组成一个新的输出序列。

首先，取出preseq的第一个元素preseq[0]，可以知道它肯定是目前正在处理的整棵二叉树的根结点，接着在inseq中寻找这个根结点，于是就可以把inseq分成三段，第一段是左子树的中序输出结果inseq1，第二段是根结点本身inseq2，第三段则是右子树的中序输出结果inseq3。同样的，preseq也可以分成三部分：第一个元素就是根结点，记为preseq1，然后是和inseq1等长的一个子串，也就是左子树的先序遍历的输出结果，剩下的，就是和inseq3等长的子串，即右子树的先序遍历输出结果了。既然有得到了先序和中序遍历的输出结果各一对，那么接下来只要对对应的一对输出结果递归调用原来的功能就可以了。递归的base case，就是输出结果只有一个元素的情况。这时候只需要生成一个没有左右子树的节点即可。

我写了两个版本，第一个是很简单很直接的实现，就是完全按照上面所说的思路来做的，因此其中充满了字符串的复制操作，详见代码（其中的make_tree_by_prein函数就是实现了上面的算法的代码）

第二个版本避免了字符串的复制操作，不过没有第一个版本的make_tree_by_prein函数那么好理解了。这里只有修改后的make_tree_by_prein函数的代码

CommonLisp和Java的版本

C语言中的第二个版本在CommonLisp和Java里面可以改得更好一点，这多亏了CommonLisp的闭包特性和Java的OO方式。在C实现的第二个版本中，make_tree_by_prein函数有两个参数，而辅助函数make_tree_aux则需要两个参数。其中参数preseq和inseq是两个在传递过程中完成不会被修改的参数，它们之所以被作为参数，仅仅是因为C语言中只有两种方式在函数间共享一些信息：

• 函数参数
• 全局变量

因为不想使用全局变量，所以只好在参数列表中动手脚了，不过在CommonLisp和Java的实现，就有办法可以在函数之间以受控的方式共享信息。例如下面用CommonLisp实现的make-tree-by-prein函数

函数make-tree-by-prein利用labels在函数体内部定义了一个闭包aux，preseq和inseq则是在词法范围内可见的变量，因为在aux内部依然可以访问到它们，这样就不需要将它们作为aux的两个参数来进行传递了。而Java的实现也是类似的，在Java中方法从属于类，并且它们可以共享同一个类的实例中的所有变量，因此直接使用这些变量即可，代码如下（因为Java同样没有办法定义内部函数的关系，所以只好定义一个用private修饰的方法makeTreeAux了。）

不是有人说吗？OO是穷人的闭包；闭包是穷人的OO;-)

后记

总算把讲思路贴代码的东西弄完了，可以好好扯淡一番了=。=话说上课的时候有个考研的同学找我讲话（班里的一名胖子，在算法方面有很厉害的嗅觉），就是问我对于用算法来实现“根据先序和中序输出结果如何构造二叉树”有没有思路。递归的方法其实很容易就可以想出来了，加之我之前已经想过这类题目要怎么系统地解决，所以很快就说出来了。然后我就觉得用C语言可以像上面那样写出一个高效（即没什么字符串复制操作）的版本，接着又想到这个可以用Lisp（或者其它带闭包的语言）来实现得更好，又想到了用Java也可以实现闭包的那类效果，再接着又觉得可以发篇文章来讨论讨论，于是就有这样的一篇东西了。

对于具体实现某个功能的技术，我貌似没有特别地挑剔，甚至可以说，对于加入到编程语言中的任何特性，我都没有太挑剔的，只要好用，那么我就很可能会接纳——当然了，我也无法保证自己在找到一个反例之后不会把这句话给改掉当作自己没有这么说过，不过暂时没有想到这种情况，所以就先当作我是这样的人吧。举个例子，对于Haskell我很喜欢，也很喜欢纯函数语言的说法，即“纯函数是非常有利于程序编写的”。不过对于副作用我也没有持完全拒绝的态度，即使我在编程的过程中也会尽量遵循函数式编程的规矩（尽量避免副作用）。可是副作用实际上避无可避，倒不如拥抱它们。或许正是因为这个原因，我才会喜欢OCaml更甚于Haskell吧——至少目前是这样的。

我也喜欢惰性计算，尤其是其带来的效果——无限长的列表推到看起来实在是帅得不行，并且还可以使得编写的程序拥有了函数式的外观和命令式的效率（例如《SICP》中举的例子，用惰性计算结合map、filter和reduce）。拥有惰性计算有利无害，何乐而不为呢～或许也正是因为自己对特性的需求是多多益善，所以才喜欢Common Lisp吧。

链子涂色问题的动态规划解法

话说大四已经开始了一个半月了，自己自从开学以来也一直在找工作，相继投了很多家IT公司。可悲的是，笔试过后就完全没有回音了——参加了多益网络的笔试两天后倒是有回音，只是收到的是拒绝的邮件QAQ。说实话，现在对于自己能不能够顺利地找到工作还是很担忧的，所以最近开始了紧张的复习。不过自己实在是懒，所以也没有像别人考研那么地拼命，只是在刷完微博读完邮件逛完豆瓣后开始看一些讲数据结构和算法的书罢了。至于是否真的有效，我也不清楚，毕竟笔试题目也不一定就完全考察这些内容的。不过按照目前的几次经验来讲，考察数据结构和算法的擦边球也有不少，可以说也是为了日后的面试准备一下吧，如果有面试的话……QAQ。

问题来源与描述

前面跑题还真严重，算是个人风格吧……话说室友去了一家名为CVT的公司参加笔试和面试，尽管最后第二轮被刷了，不过可以说还是挺厉害的。他在参加了笔试之后回来和我说了一道题目，大意是“给一串红绿珠子并存的链子，要求通过涂色把红色的珠子全部放到绿色的珠子的左边去，要求涂色的次数尽可能地少”。刚开始的时候没有认真听，于是就觉得这是编辑距离的变体罢了，那天晚上就把这个思路脱口而出，结果他第二天去面试面试官又拿这道题问他有没有新思路，结果估计被我害得够呛吧，惭愧。

题目其实有蹊跷，因为编辑距离是有前提的，那就是做变换的过程中要可以使用插入和删除操作，而那道题只允许涂色，那么也就是编辑距离中的替换操作罢了。还有另外一个和编辑距离不同的地方，那就是最终的变换目标不是唯一的，因为完全可以把链子里的珠子全部涂成一个颜色，那样就不会有红色在绿色的右边的情形了。所以，这道题目不是编辑距离的变体。唉，都怪自己太骄傲了，没有读懂题目。

动态规划的解法

前天上计算智能的课的时候，因为室友（去笔试的那位）想到了正确的线性时间的解法，所以我也不甘落后，开始在课堂上捣鼓起这道题目来。我的预感是，一般笔试题应该都可以用动态规划来做的，于是就从动态规划的角度来思考，结果也确实想到了一个办法。尽管不知道网上是不是已经有这道题的解法了，不过还是拿出来分享一下吧。

既然要使用动态规划，那么当然要按部就班地来思考。首先，就是要描述最优解的结构，也就是要找出问题解的最优子结构。为了便于描述，先约定一些记法。对于珠子和链子这种东西，可以把它们适当地抽象为元素和数组，用R代表红色而用G代表绿色，同时用S表示整个数组。数组的长度记为S.len，数组的第n个元素记为S[n]，而把最后一个元素拿掉之后的数组记为S[1..(S.len-1)]（类似于Python中的数组slice的写法）。对具体的数组实施变换，即涂色操作的功能就命名为F，它是一个二元函数，第一个参数是数组，第二个参数是位于数组之后的元素。为什么要这样子定义，而不是定义为一元函数呢？

不一样的最优子结构

对于数组的最后一个元素S[S.len]，它只有两种可能：

• S[S.len]为R；
• S[S.len]为G。

并且如果本来是红色R的，那么可以涂成绿色G的；本来是绿色G的，可以涂成红色R。可是对于一个珠子，是不是真的可以随意地对它涂色的呢？显然不是的。例如，如果已经确定了整个数组S的下一个元素是红色R的，那么S[S.len]就无论如何也不能涂成绿色，因为这样一来就绝对无法得到红色全在绿色右边的链子了。所以，如果操作F是最优的，即F对于一个数组S以及给定的下一个元素a，它的涂色次数最少，那么：

• 如果a为R，那么F肯定是把前缀S[1..(S.len-1)]也给全部涂成了红色；
• 如果a为G，那么F对于数组S的前缀S[1..(S.len-1)]的涂色次数肯定也是最少的。

上述的第二条，正是解的最优子结构。

递归定义最优解的值

显然，最优解的值也就是最优解的衡量标准，即需要对原来的数组进行的涂色的次数。既然要递归定义，那么就要考虑递归的一般情形（也就是需要递归的情形）以及基准的情形。对于下一个元素a为红色的情况，只能继续选择把目前处理的数组的最后一个元素也涂成红色，因此如果原来的数组最后一个元素S[S.len]不是红色，那么就需要一次涂色操作，如果是那么就不需要；对于下一个元素为绿色的情况，需要分别考虑要不要涂改最后一个元素的问题。如果涂，那么就增加一次操作，不涂就不需要。在a为绿色的两个分支中，涂成（或者保留）红色末尾元素的情形，和a为红色的情况的递归是一样，因此这里确实存在重叠子问题——动态规划的另一个要求。至于基准情况，则是当数组只有两个元素时的情况。此时，只能是GG、GR、RG、GG这四种，除了GR需要进行一次涂色之外，其它的均不需要涂色。

用数学公式来表示递归的情形可能更清楚：

其中diff函数判断两个参数是否相等。如果相等，那么就返回0，否则返回1。也就是在从第一个参数变换到第二个参数时所需要的涂色次数。

按自底向上的方式计算最优解的值

在思考如何自底向上的时候，我采用的办法是先自顶向下地演示一遍。如下图所示，其中入口功能的名字为G，例子所使用的数组为RGRG：

显然这里需要构造一个表格来对F过程的中间结果进行存储，因为F是一个二元的函数。尽管F的第一个参数是一个数组，可是原来的数组是不会变的，所以只需要记住当前处理的数组是由原来的数组的前多少个元素组成的前缀即可，因此F的第一个参数可以用数字来代替。因此，在处理过程中需要的是这样的一张表：

（不好意思，图中的空格没有对齐>_<）

那么如何自底向上呢？首先对于参数为1而下一个元素为R的情况，因为是递归函数的基准情况，所以可以直接得到F(1, R)=F([R], R)为0，于是填入0；同样第二行的第一个空格的值也为0。当需要填写第一行的第二个空格的时候，可以知道因为下一个元素为R，所以此处的值只与之前的末尾元素亦为红色R的情形有关，所以这个值只与第一行的前一个值有关，并且此时的元素S[2]为G与R不同，因此需要变换，故增加一；而第二行的第二个空格的值取决于前一列的两个格子的值。此时即计算G([RGG])的值，所以取F([RG], G)和F([RG], R)+1的较小值，即1。其它空格以此类推，最终结果为：

由计算出的结果构造一个最优解

显然，最后一列的结果就是所要的值，例如上面的数组[RGRG]的最少涂色次数是1，并且操作是将第二个位置上的G涂成R。这样的操作反映在中间结果中，就是先找出最后一列的元素的值最小的那一行，例如上面就是第二行。然后就是在所有的列中找出所有与下一列的值不一样的列，将其对应的珠子的颜色翻转。例如在上面的表格中，就是将第二列的G涂成R，因为G对应的数字0不同于下一列的数字1。好吧，这一次，我就不给代码了，因为我还没有写出来;)