动态规划dynamical programming，简称dp。了解它请参考《数学之美》第12章和《算法导论》第2版第15章，这里就不重复了。
《算法导论》第15章的“装配线调度”问题是非常好的dp学习算法，用数学语言包装之后有点难懂，我用python写了个简化版，只需要看图15-2，再看下面的代码，就知道dp是怎么回事了。
-----------------------------------------------------
#!/usr/bin/env python
#!-*- coding:utf-8 -*-
#底盘进入装配线需要的时间
e1 = 2
e2 = 4
#底盘离开装配线需要的时间
s1 = 3
s2 = 2
#底盘在装配线上每个装配站的处理时间
a1 = [7, 9, 3, 4, 8, 4]
a2 = [8, 5, 6, 4, 5, 7]
#底盘在装配件之间移动时需要的时间。
t1 = [2, 3, 1, 3, 4]
t2 = [2, 1, 2, 2, 1]
#初始化f1和f2，也就是用进入装配线时间和第一个装配站用时之和
f1 = [e1 + a1[0］
f2 = [e2 + a2[0］
#这一块，就是用dp的方式，分别计算两条装配线的最短时间装配时间
i = 1
l1 = []
l2 = []
while i < 6:
if (f1[i-1] + a1[i] < f2[i-1]+a1[i]+t2[i-1]):
f1.append(f1[i-1] + a1[i])
l1.append(1)
else:
f1.append(f2[i-1]+a1[i]+t2[i-1])
l1.append(2)
if (f2[i-1] + a2[i] < f1[i-1]+a2[i]+t1[i-1]):
f2.append(f2[i-1] + a2[i])
l2.append(2)
else:
f2.append(f1[i-1]+a2[i]+t1[i-1])
l2.append(1)
i += 1
#离开装配站
f1.append(f1[-1]+s1)
f2.append(f2[-1]+s2)
#f1和f2的最后一个元素分别是38和39，所以从第一条装配线出来的更快。l1和l2计算了底盘在两线之间的移动状态。
print f1
print f2
print l1
print l2
-----------------------------------------------------
关于中文分词：
注：代码和例子借鉴了http://www.2cto.com/kf/201203/123935.html，向原作者致谢。
《数学之美》第4章是中文分词问题。中文是句子，比如说，"其中最简单的就是最大匹配的中文分词"，如果要让计算机理解这个句子，要先把它拆成若干个词组。根据统计模型，每个词组有不同的出现频率，这个频率是语料决定的，业内的做法是，找一个很大的文本资料，比如几十年里的人民日报，把里面的所有新闻拆成一个一个的词组，然后计算这些词组在所有新闻里的出现次数，由此生成一个巨大的词频表。
搜狗试验室做了一个词频表，在这里http://www.sogou.com/labs/dl/w.html，下载在这里http://download.labs.sogou.com/dl/sogoulabdown/SogouW/SogouW.tar.gz。这个词频表有157202个高频词。本文使用这个词频表。
如果要把一个句子拆成几个词组，应该尽量把它拆成高频词，越高越好。高频，就是高概率。
处理一个文本，如果要把它拆成概率最高的词组，最简单的方式是遍历所有组合，然后找概率最高的，这在算法上是指数复杂度，太慢，用dp算法处理最合适。
以"其中最简单的就是最大匹配的中文分词"为例，dp算法是这么做的：
1) 从最后一个字往第一个字处理。
2)最后一个字是“词”，查词频表，看它有没有出现，如果出现了，记下词频数，如果没出现，就认为它的词频数默认值是1。然后计算概率，它的概率就是“词频数/157202”，157202就是词频表里的词组总数。很显然，词频表没有这个字，于是它的概率就是1/157202，记作p[16] = 1/157202，p表示概率，16是这个字在句子里的坐标，这个句子一共17个字，坐标从0开始计算，所以它是第16位。
3) 倒数第二个字是“分”。这一次要处理的是两个字，也就是最后一个字和这一个字的组合，也就是“分词”，“分词”是全句的一部分，也就是子句。如何让“分词”这个子句的出现概率最高呢？先从“分”拆开，查它在词频表的词频，词频表没有，所以p[15]=1/157202，如果把“分“和”词”拆开计算概率，那么子句的整体概率就是p[15]*p[16]=(1/157202)*(1/157202)。如果从“词”拆，这么拆的话，“分词”就是一个整体了，查词频表，它的词频数是390214，所以它的概率是390214/157202，也就是说，子句的整体概率是390214/157202，这个概率比前面的高，于是更新一下p[15]=390214/157202。
4) 倒数第三个字是“文”。这一次，要处理三个字“文词汇”。按照跟上面相似的步骤，最佳的分割方式是“文 词汇”。
5) 倒数第四个字是“中”。这一次，要处理四个字“中文词汇”。按照跟上面相似的步骤，最佳的分割方式是“中文 词汇”。
....
以此类推，处理整个句子。
这里的关键是：如果让整个句子的分词结果是概率最高的，那么，每个子句的分词结果也必然是最高的，否则，总是可以找到一个更好的拆分子句方式，让整句的分词结果概率更高。dp的做法是，先从最短的子句开始，找概率最高的分词方式，然后逐步扩展到整句，于是整句的分词概率也就是最高的。
下面是代码：
------------------------------------------
#!/usr/bin/env python
#!-*- coding:utf-8 -*-
import collections
#d是字典，存储从词频表读取的词频数据。defaultdic的好处是，如果词频表没有某个词组，就返回1。
d = collections.defaultdict(lambda:1)
#从词频表里读取词频数，SogouLabDic.dic需要下载，然后放到跟源代码相同的目录。
def init(filename = "SogouLabDic.dic"):
total = 0
for line in open(filename).readlines():
word, freq = line.split(‘\t‘)[0:2]
total += 1
try:
d[word.decode(‘gbk‘)] = int(freq)
except:
d[word] = int(freq)
d[‘_t_‘] = total
#分词函数
def solve(s):
l = len(s)
#p表示概率，初始值是0
p = [0 for i in range(l+1)]
#最后一位是为了方便计算，设置成1
p[l] = 1
#词频数太大了，不能使用除法，会有精度问题，把分子分母分开存储
div = [1 for i in range(l+1)]
#记录拆分位置
t = [1 for i in range(l)]
#dp算法做拆分
for i in range(l-1,-1, -1):
print "\ni = ", i
for k in range(1, l-i+1):
print " k = ", k
if k > 1 and d[s[i:i+k］ == 1:
print " continue"
continue
#判断子句的概率大小，以计算拆分位置
if d[s[i:i+k］*p[i+k]*div[i] > p[i]*d[‘_t_‘]*div[i+k]:
p[i] = d[s[i:i+k］*p[i+k]
div[i] = d[‘_t_‘] * div[i+k]
t[i] = k
i = 0
while i < l:
print s[i:i+t[i］.encode("utf8"),
i = i+t[i]
init()
s="其中最简单的就是最大匹配的中文分词"
s=s.decode(‘utf8‘)
solve(s)
------------------------------------------
这句话的拆分结果是：“其中 最简单 的 就是 最大 匹配 的 中文 分词”，效果还不错哦！
再搞个更长一点的吧，这句话是网上对某个餐厅的一段评论：
“接着来到港汇。。皮和鹿都中了这家的现金券。。甜品阿拉果断要来蹭一下。。位于港汇的2楼，一堆服装店的里面。。位置真的有点难找啊。。绕了一大圈最后才找到的。。其实就在一个角落，从某个门进来就可以直接抵达了。。咳咳，我想说门口的胡宇崴我根本不认识。。店内的环境还可以吧，所谓的女仆啥的还有带着面具跳舞之类的我是完全没看到。。阿拉是晚上7点左右去的，是时间不对么？？？落座后服务员马上每人端上一杯水。。服务还是很周到的。。他家有wifi，密码会写在收银条上。。为了得知密码还得赶紧点单啊。。真是。。西西里海鲜意大利面，68米。。端上来时候就觉得有点坑爹了，菜单上的摆盘多精致啊，面都堆成一座小山的样子，虾什么也大多了。。面的口味一般，茄汁味不浓，吃起面来就觉得没啥味道。。里面有虾、青口贝、鱿鱼什么的，阿拉什么都没吃味道就不予评价了。。法式金砖，72米。。小块吐司上面顶着一个冰淇淋球，看着还是比较美貌的。。摆盘下方则是巧克力酱画的高音谱号和音符，对跳舞香水名字的点题吧。。吐司相对偏软了点，还可以烤的更脆。。比起坑爹的意面，甜品的口味还是能令人满意的。。甜品ok，主食不灵。。"
分词的结果是：
“接着 来到 港 汇 。 。 皮 和 鹿 都 中了 这家 的 现金 券 。 。 甜品 阿拉 果断 要来 蹭 一下 。 。 位于 港 汇 的 2 楼 ， 一堆 服装店 的 里面 。 。 位置 真 的 有点 难找 啊 。 。 绕了 一大 圈 最后 才 找到 的 。 。 其实 就在 一个 角落 ， 从 某个 门 进来 就可以 直接 抵达
了 。 。 咳咳 ， 我想 说 门口 的 胡 宇 崴 我根本 不认识 。 。 店内 的 环境 还可以 吧 ， 所谓 的 女仆 啥 的 还有 带着 面具 跳舞 之类 的 我是 完全 没 看到 。 。 阿拉 是 晚上 7 点 左右 去 的 ， 是 时间 不对 么 ？ ？ ？ 落座 后 服务员 马上 每人 端 上一 杯水 。 。 服务 还是 很 周到 的 。 。 他家 有 w i f i ， 密码 会 写在 收银 条 上 。 。 为了 得知 密码 还得 赶紧 点 单 啊 。 。 真是 。 。 西西里 海鲜 意大利
面 ， 6 8 米 。 。 端 上来 时候 就 觉得 有点 坑 爹 了 ， 菜单 上 的 摆 盘 多 精致 啊 ， 面 都 堆成 一座 小山 的 样子 ， 虾 什么 也 大多 了 。 。 面 的 口味 一般 ， 茄 汁 味 不 浓 ， 吃 起 面 来 就 觉得 没啥 味道 。 。 里面 有 虾 、 青口 贝 、 鱿鱼 什么 的 ， 阿拉 什么 都没 吃 味道 就不 予 评价 了 。 。 法式 金砖 ， 7 2 米 。 。 小块 吐 司 上面 顶着 一个 冰淇淋 球 ， 看着 还是 比较 美貌 的 。 。 摆
盘 下方 则是 巧克力 酱 画 的 高音 谱 号 和 音符 ， 对 跳舞 香水 名字 的 点题 吧 。 。 吐 司 相对 偏 软了 点 ， 还可以 烤 的 更 脆 。 。 比起 坑 爹 的 意 面 ， 甜品 的 口味 还是 能 令人 满意 的 。 。 甜品 o k ， 主食 不灵 。 。”
是不是觉得差强人意？这就是自然语言处理的困难之处，不通用，跟行业相关。选择合适的语料库很关键。
另外，python有一个开源的分词包，叫“jieba”，有兴趣的可以试用一下。
广告时间：请关注微信公众号“美食挖”，谢谢！动态规划和中文分词,布布扣,bubuko.com
动态规划和中文分词
原文：http://blog.csdn.net/lizhe_dashuju/article/details/21598811
