Rod Cutting
有一段長的鋼管势木，根據(jù)市場需求蛛倦，鋼管可以切成1m，2m啦桌，3m溯壶，4m出售，每種尺寸的鋼管價(jià)格不同甫男，如果有一段10m長的鋼管且改，如何切割可以使利益最大化呢？如下圖所示：
我們可以想到用分治的辦法解決板驳，例如又跛，切一刀，遞歸去找余下長度的最優(yōu)若治，切兩刀慨蓝，遞歸去找余下長度的最優(yōu)，一次類推端幼，這是一個(gè)指數(shù)級增長的計(jì)算量礼烈。
上述不是一個(gè)好辦法，怎么優(yōu)化呢婆跑？我們可以依次去找切成1塊的最優(yōu)此熬、兩塊的最優(yōu)、三塊最優(yōu)滑进，以此類推摹迷，并將此記錄下來，如下表所示郊供。然后在求余下的最優(yōu)峡碉，看記錄表有沒有此長度的記錄，有的話直接獲取驮审，沒有的話在去計(jì)算鲫寄。
| 長度 | 最優(yōu)切割方式 | 價(jià)值 |
|---|---|---|
| 1 | 不切 | 1 |
| 2 | 不切 | 5 |
| 3 | 不切 | 8 |
| ... | ... | ... |
Sequence Matching
在生物學(xué)中，人類DNA由4個(gè)堿基組成：腺嘌呤（A）疯淫，胸腺嘧啶（T）地来，鳥嘌呤（G），胞嘧啶（C）熙掺。如果想判斷兩段DNA相似程度未斑，可以通過編輯距離（edit distance）來判定，即一個(gè)字符串通過刪除币绩、修改轉(zhuǎn)變?yōu)榱硗庖粋€(gè)字符串蜡秽，已知每種操作的成本如下：
上圖中左邊的編輯距離是8府阀，右邊的是7.
在每次匹配中，我們都可以執(zhí)行兩種操作：1.當(dāng)前字符匹配（相等成本為0芽突，修改為1）试浙；2.刪除其中一個(gè)字符（成本為2）。參考如下示例：
在解決此問題中寞蚌，因?yàn)槊看纹ヅ涠紩婕暗街貜?fù)的計(jì)算田巴，我們可以把已匹配的結(jié)果，存儲下來方便復(fù)用挟秤。比如上圖中壹哺，我們知道了兩字符串后兩位的最優(yōu)編輯距離是1，并且知道了其他操作的編輯距離艘刚，方便后面復(fù)用斗躏。
我們將兩個(gè)字符串變成了2維矩陣，中間的每一個(gè)格代表兩字符串的編輯距離（從后向前）昔脯。比如“CC”和“A”的編輯距離是3啄糙，即C和A進(jìn)行修改成本為1，刪除最后的C成本為2. 再比如“AACAGTTACC”和“”編輯距離是20云稚，即進(jìn)行了10次刪除操作隧饼，變?yōu)榭沾Ｓ?jì)算公式如下：
上述公式表明匹配到當(dāng)前字符串S1[i: ]和S2[j: ]時(shí)静陈，可以刪除某一字符串的字符（成本為2）然后加上已經(jīng)計(jì)算過的兩字符串的編輯距離燕雁；或當(dāng)前字符進(jìn)行匹配（成本：相同為0，修改為1）然后加上已經(jīng)計(jì)算過的兩字符串的編輯距離鲸拥。
兩字符串完整的編輯距離如下圖所示拐格，我們可以找到最優(yōu)的匹配方式：首先是A和T匹配，然后是A和A匹配刑赶，然后刪除掉行字符串的C捏浊，然后A和A匹配，依次類推撞叨。
