动态规划

Rod Cutting

有一段长的钢管，根据市场需求，钢管可以切成1m，2m，3m，4m出售，每种尺寸的钢管价格不同，如果有一段10m长的钢管，如何切割可以使利益最大化呢？如下图所示：

rod-cutting.png

我们可以想到用分治的办法解决，例如，切一刀，递归去找余下长度的最优，切两刀，递归去找余下长度的最优，一次类推，这是一个指数级增长的计算量。

rod-cut-2.png

上述不是一个好办法，怎么优化呢？我们可以依次去找切成1块的最优、两块的最优、三块最优，以此类推，并将此记录下来，如下表所示。然后在求余下的最优，看记录表有没有此长度的记录，有的话直接获取，没有的话在去计算。

长度	最优切割方式	价值
1	不切	1
2	不切	5
3	不切	8
...	...	...

rod-cut-3.png

Sequence Matching

在生物学中，人类DNA由4个碱基组成：腺嘌呤（A），胸腺嘧啶（T），鸟嘌呤（G），胞嘧啶（C）。如果想判断两段DNA相似程度，可以通过编辑距离（edit distance）来判定，即一个字符串通过删除、修改转变为另外一个字符串，已知每种操作的成本如下：

动态规划4.png

上图中左边的编辑距离是8，右边的是7.

在每次匹配中，我们都可以执行两种操作：1.当前字符匹配（相等成本为0，修改为1）；2.删除其中一个字符（成本为2）。参考如下示例：

动态规划5.png

在解决此问题中，因为每次匹配都会涉及到重复的计算，我们可以把已匹配的结果，存储下来方便复用。比如上图中，我们知道了两字符串后两位的最优编辑距离是1，并且知道了其他操作的编辑距离，方便后面复用。

动态规划6.png

我们将两个字符串变成了2维矩阵，中间的每一个格代表两字符串的编辑距离（从后向前）。比如“CC”和“A”的编辑距离是3，即C和A进行修改成本为1，删除最后的C成本为2. 再比如“AACAGTTACC”和“”编辑距离是20，即进行了10次删除操作，变为空串。计算公式如下：

动态规划7.png

上述公式表明匹配到当前字符串S1[i: ]和S2[j: ]时，可以删除某一字符串的字符（成本为2）然后加上已经计算过的两字符串的编辑距离；或当前字符进行匹配（成本：相同为0，修改为1）然后加上已经计算过的两字符串的编辑距离。

两字符串完整的编辑距离如下图所示，我们可以找到最优的匹配方式：首先是A和T匹配，然后是A和A匹配，然后删除掉行字符串的C，然后A和A匹配，依次类推。

动态规划8.png

参考

CS50