問題描述
??子序列是指贫母，從序列中選出一些子元素文兑，需滿足其前后關(guān)系與在原序列中相同；公共是指該序列同時(shí)是兩個(gè)序列的子序列腺劣。如兩個(gè)序列{4绿贞，2，1 橘原，6樟蠕，5，8靠柑，13，18吓懈，9歼冰，5}和 {3，2耻警，1隔嫡，9，10甘穿，6腮恩，5，9}温兼，{2秸滴，1}和{1，6募判，5}都是它們的公共子序列荡含，顯然，這不是最長的届垫。那么如何求解兩個(gè)序列的最長公共子序列（LCS）释液？
分析
??LCS具有最優(yōu)子結(jié)構(gòu)。令和
為兩個(gè)序列装处，
為X和Y的任意LCS误债。
- 如果
，則
且
是
和
的一個(gè)LCS；
- 如果
寝蹈，那么
李命，意味著
是
的一個(gè)LCS;
- 如果
躺盛，意味著
和
??從上面分析可以看出项戴，當(dāng)時(shí)，需要計(jì)算
和
的一個(gè)LCS槽惫；當(dāng)
時(shí)周叮，需要分別計(jì)算
和
的一個(gè)LCS、
和
的一個(gè)LCS界斜。具有很明顯的狀態(tài)轉(zhuǎn)移含義仿耽，這些重疊的子問題可以用動(dòng)態(tài)規(guī)劃方法快速解決。
??根據(jù)LCS問題的最優(yōu)子結(jié)構(gòu)性質(zhì)各薇，有如下遞歸公式：
狀態(tài)轉(zhuǎn)移方程
??二維數(shù)組dp[i][j]表示序列與序列
的最長公共子序列長度项贺。根據(jù)題目中的數(shù)據(jù)，可以畫出如下序列增長過程峭判，看出此動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為
开缎，因?yàn)槊總€(gè)表項(xiàng)的計(jì)算時(shí)間是
.
序列增長過程
代碼實(shí)現(xiàn)
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 205;
int dp[maxn][maxn];
int arr1[maxn], arr2[maxn];
int main()
{
int n, m;
memset(dp,0,sizeof(dp));
memset(arr1,0,sizeof(arr1));
memset(arr2,0,sizeof(arr2));
cin >> n; for(int i=1;i<=n;i++) cin>>arr1[i];
cin >> m; for(int i=1;i<=m;i++) cin>>arr2[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(arr1[i]==arr2[j]) dp[i][j] = dp[i-1][j-1]+1;
else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
cout << dp[n][m];
return 0;
}
Tips
- 最長公共子序列和編輯距離，都是衡量字符串相似度的指標(biāo)林螃，也都是動(dòng)態(tài)規(guī)劃算法的典型奕删。
