前段時(shí)間研究過(guò)如何求最長(zhǎng)連續(xù)公共子序列和最長(zhǎng)連續(xù)子字符串，以前一個(gè)同學(xué)正好問(wèn)起來(lái)，這里貼出來(lái)解法：
問(wèn)題的關(guān)鍵還是如何定義子問(wèn)題，假設(shè)有：
Xm = x1 x2 x3 ... xm
Yn = y1 y2 y3 ... yn

1. 最長(zhǎng)公共子序列(不必連續(xù))
定義f(m, n)為Xm和Yn之間最長(zhǎng)的子序列的長(zhǎng)度
于是有f(m, 0) = f(0, m) = 0
如果xm != yn, 則f(m, n) = max{ f(m-1, n), f(m, n-1) }
如果xm = yn，則f(m, n) = f(m-1, n-1) + 1
問(wèn)題歸結(jié)于求f(m, n)。依照公式用Bottom-up DP可解。

2. 最長(zhǎng)連續(xù)子字符串(必須是連續(xù)的)
定義f(m, n)為Xm和Yn之間最長(zhǎng)的子字符串的長(zhǎng)度并且該子字符串結(jié)束于Xm & Yn。因?yàn)橐笫沁B續(xù)的，所以定義f的時(shí)候多了一個(gè)要求字符串結(jié)束于Xm & Yn
于是有f(m, 0) = f(0, m) = 0
如果xm != yn, 則f(m, n) = 0
如果xm = yn, 則f(m, n) = f(m-1, n-1) + 1
因?yàn)樽铋L(zhǎng)字符串不一定結(jié)束于Xm / Yn末尾，所以這里必須求得所有可能的f(p, q) | 0 < p < m, 0 < q < n, 最大的f(p, q)就是解。依照公式用Bottom-up DP可解。

轉(zhuǎn)載自：http://blog.csdn.net/atfield/archive/2007/01/28/1496132.aspx

我的補(bǔ)充：最長(zhǎng)連續(xù)子字符串問(wèn)題與最大子段和問(wèn)題有點(diǎn)類似。