最長公共子序列求解問題是一種典型的動态規劃問題。此文章以http://nyoj.top/problem/1409 或http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=36為例說明最長子序列的動态規劃算法如何優化。
關于最長公共子序列的動态規劃，見https://blog.csdn.net/hrn1216/article/details/51534607
正常方法
#include<iostream>
#include<algorithm>
#include<string>//LCS（Longest Common Subsequence)
using namespace std;
int dp[1001][1001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
short N;
string s1, s2;
unsigned n1, n2,i,j;
cin >> N;
while (N--)
{
cin >> s1 >> s2;
n1 = s1.size();
n2 = s2.size();
for (i = 0; i <= n1; i++)dp[i][0] = 0;
for (j = 0; j <=n2; j++)dp[0][j] = 0;
for(i=1;i<=n1;i++)
for (j = 1; j <= n2; j++)
dp[i][j] = (s1[i-1] == s2[j-1]) ? dp[i - 1][j - 1] + 1 : max(dp[i][j - 1], dp[i - 1][j]);
cout << dp[n1][n2] << endl;
}
return 0;
}
注意到，此處定義了一個nxm的二維數組，空間開銷很大。實際上通過觀察建立的最優值的遞歸式
發現求解C[i,j]的值總是建立在二維數組第
i行某一列元素或者第i-1行某一列元素基礎上的，如果不需要求解最長公共子序列是什麼，隻需要求解其長度，那麼我們可以建立一個2xn的滾動數組代替nxm的數組來實作空間優化，這種方法隻需要用到cur層和pre層的資料，通過cur和pre的不斷交換實作mxn的數組功能。
空間優化後的代碼
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N,cur,pre;
string s1,s2;
int dp[2][1001];
unsigned len1,len2,i,j;
cin>>N;
while(N--)
{
cin>>s1>>s2;
len1=s1.size();
len2=s2.size();
cur=1;
pre=0;
for(i=0;i<=len2;i++)dp[0][i]=0;
dp[1][0]=0;
for(i=1;i<=len1;i++)
{
for(j=1;j<=len2;j++)
{
if(s1[i-1]==s2[j-1])
dp[cur][j]=dp[pre][j-1]+1;
else
dp[cur][j]=max(dp[cur][j-1],dp[pre][j]);
}
swap(cur,pre);
}
cout<<dp[pre][len2]<<endl;
}
return 0;
}
此時的空間複雜度為o（n），時間複雜度還是o（nxm），此方法使用的前提是隻需要求解最大公共子序列長度。
對空間繼續優化
讓我們在看那段代碼,在橫向掃描并儲存數組的時候，也起到了個滑動的功能。那我們能不能隻有一個縱向的數組呢？
我們在更新數組時，會發現在更新時可能需要dp[pre][j]和dp[cur][j-1] dp[pre][j-1]的值，實際上用一維數組dp[n]即可。在将要更新dp[j]前，dp[j]值即是剛才dp[pre][j]的值,dp[cur][j-1]的值對應現在dp[j-1]的值。剛才dp[pre][j-1]的值可以儲存在一個臨時變量old中。代碼如下：
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int N;
string s1, s2;
int dp[1001],tmp,old;
unsigned len1, len2, i, j;
cin >> N;
while (N--)
{
cin >> s1 >> s2;
len1 = s1.size();
len2 = s2.size();
for (i = 0; i <= len2; i++)dp[i] = 0;
for (i = 1; i <= len1; i++)
{
old = dp[0];//dp[0]代表原本dp[i-1][0]
for (j = 1; j <= len2; j++)
{
tmp = dp[j];//tmp代表dp[i-1][j]的值
if (s1[i - 1] == s2[j - 1])
dp[j] = old + 1;//代表dp[i-1][j-1]+1
else
dp[j] = max(dp[j - 1], dp[j]);//dp[j-1]代表dp[i][j-1]
//更新值後dp[j]代表dp[i][j]
old = tmp;//保留dp[i-1][j]的值留給下一步求解最優解時使用
}
}
cout << dp[len2] << endl;
}
return 0;
}
注：這種方法雖然能夠減少一半的空間開銷，但是空間複雜度仍為o(n),代碼較難了解，故對空間要求不高時使用第二種方法即可。此外，對于求解LCS問題，還有一種思路是轉化為最大上升子序列，并采用二分搜尋，這種方法可以把平均時間複雜度降到nlogn，但是存在極端情況效率比普通的動态規劃方法效率更低，且轉化過程中也有一定的時間空間開銷，當輸入的序列中各種符号混合時構造上升子序列較麻煩，我認為一般情況下沒必要去使用。