Rod Cutting
有一段长的钢管，根据市场需求，钢管可以切成1m，2m，3m，4m出售，每种尺寸的钢管价格不同，如果有一段10m长的钢管，如何切割可以使利益最大化呢？如下图所示：
我们可以想到用分治的办法解决，例如，切一刀，递归去找余下长度的最优，切两刀，递归去找余下长度的最优，一次类推，这是一个指数级增长的计算量。
上述不是一个好办法，怎么优化呢？我们可以依次去找切成1块的最优、两块的最优、三块最优，以此类推，并将此记录下来，如下表所示。然后在求余下的最优，看记录表有没有此长度的记录，有的话直接获取，没有的话在去计算。
| 长度 | 最优切割方式 | 价值 |
|---|---|---|
| 1 | 不切 | 1 |
| 2 | 不切 | 5 |
| 3 | 不切 | 8 |
| ... | ... | ... |
Sequence Matching
在生物学中，人类DNA由4个碱基组成：腺嘌呤（A），胸腺嘧啶（T），鸟嘌呤（G），胞嘧啶（C）。如果想判断两段DNA相似程度，可以通过编辑距离（edit distance）来判定，即一个字符串通过删除、修改转变为另外一个字符串，已知每种操作的成本如下：
上图中左边的编辑距离是8，右边的是7.
在每次匹配中，我们都可以执行两种操作：1.当前字符匹配（相等成本为0，修改为1）；2.删除其中一个字符（成本为2）。参考如下示例：
在解决此问题中，因为每次匹配都会涉及到重复的计算，我们可以把已匹配的结果，存储下来方便复用。比如上图中，我们知道了两字符串后两位的最优编辑距离是1，并且知道了其他操作的编辑距离，方便后面复用。
我们将两个字符串变成了2维矩阵，中间的每一个格代表两字符串的编辑距离（从后向前）。比如“CC”和“A”的编辑距离是3，即C和A进行修改成本为1，删除最后的C成本为2. 再比如“AACAGTTACC”和“”编辑距离是20，即进行了10次删除操作，变为空串。计算公式如下：
上述公式表明匹配到当前字符串S1[i: ]和S2[j: ]时，可以删除某一字符串的字符（成本为2）然后加上已经计算过的两字符串的编辑距离；或当前字符进行匹配（成本：相同为0，修改为1）然后加上已经计算过的两字符串的编辑距离。
两字符串完整的编辑距离如下图所示，我们可以找到最优的匹配方式：首先是A和T匹配，然后是A和A匹配，然后删除掉行字符串的C，然后A和A匹配，依次类推。
