題目：

若序列Z是序列X的子序列，又是Y的子序列，則稱Z是序列X與Y的公共子序列。例如序列"bcba"是序列"abcbdab"與"bdcaba"的公共子序列。 例如，給出序列X "hahafdreghsbacdba"和序列"acdbegshbdrabsa"，如何求取這兩個(gè)序列的最長(zhǎng)公共子序列？

這道題具有典型的最優(yōu)子結(jié)構(gòu)特性，即它的最優(yōu)解一定包含子問題的最優(yōu)解，這么看使用動(dòng)態(tài)規(guī)劃來(lái)解決是比較合理的。動(dòng)態(tài)規(guī)劃解題步驟通常由三個(gè)部分構(gòu)成

1. 分階段。

2. 狀態(tài)遷移方程。

3. 尋找最優(yōu)解。

對(duì)于這道題，字符數(shù)組a存儲(chǔ)序列X，數(shù)組b存儲(chǔ)序列Y，設(shè)i, j分別為數(shù)組a, b的指針。m[i][j]表示序列a[0] ~ a[i]與序列b[0]~b[j]的最長(zhǎng)公共子序列，當(dāng)a[i] == b[i]時(shí)，倆字符相等，最長(zhǎng)公共子序列等于m[i-1][j-1] + 1; 如果字符不等，則

m[i][j] = MAX(m[i-1][j], m[i][j-1])；這個(gè)就是狀態(tài)遷移方程。得到了狀態(tài)遷移方程，在開始遞推之前，需要知道邊界情況，這里的邊界情況就是當(dāng)i等于0時(shí)，對(duì)于任意的0 <= j <= len(b), m[i][j] = 0; 同理，當(dāng)j = 0時(shí)，任意的0 <= i <= len(a)， m[i][j] = 0。對(duì)于字符串而言，數(shù)組下標(biāo)為0是有字符的，所以說這么算會(huì)帶來(lái)處理上的不方便，既然順序不方便那就是用倒序好了，假設(shè)m[i][j]表示序列a[i] ~ a[last]與序列a[j][last]的最長(zhǎng)公共子序列長(zhǎng)度，當(dāng)i = len(a)的時(shí)候，任意的j值，m[i][j] = 0，這個(gè)也很好理解，i等于n，說明a里面沒有字符，這時(shí)候?qū)τ谌我獾膉值，m[i][j] = 0，同理對(duì)于j = len(b)，此時(shí)任意的i值，m[i][j] = 0。通常使用動(dòng)態(tài)規(guī)劃解決問題的時(shí)候，都存在兩種遞推方式，順序遞推和逆序遞推，具體使用哪種根據(jù)具體問題來(lái)決定。

得到狀態(tài)遷移方程，就可以知道最優(yōu)解了，即m[0][0]；接下來(lái)就是打印最優(yōu)解序列了，這個(gè)可以根據(jù)狀態(tài)遷移方程來(lái)判斷哪個(gè)字符在最優(yōu)解序列中。

下面是該問題的c代碼實(shí)現(xiàn)：

//最長(zhǎng)公共子串的動(dòng)態(tài)規(guī)劃解法#include <stdio.h> #include <string.h>#define MAX(a, b) ((a) > (b) ? (a) : (b))void main() {int i, j, k, n, m[30][30] = {0};char astr[30+1] = "hsbafdreghsbacdba", bstr[30+1] = "acdbegshbdrabsa";n = strlen(astr);k = strlen(bstr);printf("string A : %s\n", astr);printf("string B : %s\n", bstr);//邊界初始化for (i = 0; i < n; i++)m[i][k] = 0;for (j = 0; j < k; j++)m[n][j] = 0;//狀態(tài)遞推for (i = n - 1; i >= 0; i--){for (j = k - 1; j >= 0; j--){if (astr[i] == bstr[j])m[i][j] = m[i+1][j+1] + 1;elsem[i][j] = MAX (m[i+1][j], m[i][j+1]);}}//打印最優(yōu)解printf("最長(zhǎng)公共子串長(zhǎng)度為：%d\n", m[0][0]); for (i = 0; i < n;){for (j = 0; j < k;){if (astr[i] == bstr[j]){printf("%c", astr[i]);i++;j++;}else{if (m[i][j] == m[i+1][j])i++;elsej++;}}}printf("\n");return; }

?

參考資料：

1.?數(shù)據(jù)結(jié)構(gòu)?: C語(yǔ)言版/ 嚴(yán)蔚敏，吳偉民編著

=============================================================================================

Linux應(yīng)用程序、內(nèi)核、驅(qū)動(dòng)開發(fā)交流討論群(745510310)，感興趣的同學(xué)可以加群討論、交流、資料查找等，前進(jìn)的道路上，你不是一個(gè)人奧^_^。

總結(jié)

以上是生活随笔為你收集整理的动态规划 dp03 最长公共子串问题 c代码的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。