449
經典麵試題：最長公共子序列
1.問題描述：
什麼是最長公共子序列呢?好比一個數列 S，如果分別是兩個或多個已知數列的子序列，且是所有符合此條件序列中最長的，則S 稱為已知序列的最長公共子序列。
舉個例子，如：有兩條隨機序列，如 1 3 4 5 5 ，and 2 4 5 5 7 6，則它們的最長公共子序列便是：4 5 5。
注意最長公共子串（Longest CommonSubstring）和最長公共子序列（LongestCommon Subsequence, LCS）的區別：子串（Substring）是串的一個連續的部分，子序列（Subsequence）則是從不改變序列的順序，而從序列中去掉任意的元素而獲得的新序列；更簡略地說，前者（子串）的字符的位置必須連續，後者（子序列LCS）則不必。比如字符串acdfg同akdfc的最長公共子串為df，而他們的最長公共子序列是adf。LCS可以使用動態規劃法解決。下文具體描述。
2.解決思路：
2.1窮舉法
2.2動態規劃法
用動態規劃法首先要判斷該問題是否符合動態規劃法的條件，
(1) 最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理。
(2) 無後效性：即某階段狀態一旦確定，就不受這個狀態以後決策的影響。也就是說，某狀態以後的過程不會影響以前的狀態，隻與當前狀態有關。
（3）有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到。（該性質並不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃算法同其他算法相比就不具備優勢）
3.源碼：
// LCSTest.cpp : 定義控製台應用程序的入口點。
//
#include "stdafx.h"
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
using namespace std;
void LCS(string str1,string str2)
{
int len1 = str1.length();
int len2 = str2.length();
//int **dp = new int[len1+1][len2+1];
vector<vector<int> > dp(len1+1,vector<int>(len2+1));
//動態規劃初始值
for(int j = 0;j <= len2;j++)
dp[0][j] = 0;
for(int i = 0;i <=len1;i++)
dp[i][0] = 0;
for(int i = 0;i < len1;i++)
for(int j = 0;j < len2;j++)
{
if(str1.at(i) == str2.at(j))
{
dp[i+1][j+1]= dp[i][j]+1;
}
else if(dp[i][j+1] > dp[i+1][j])
dp[i+1][j+1] = dp[i][j+1];
else
dp[i+1][j+1] = dp[i+1][j];
}
cout<<"最長公共子序列長度為："<<dp[len1][len2]<<endl;
int ti = 0;
int tj = 0;
while(ti<len1 && tj<len2 )
{
if(str1.at(ti) == str2.at(tj))
{
cout<<str1.at(ti)<<" ";
ti++;
tj++;
}
else if(dp[ti+1][tj] >= dp[ti][tj+1])
ti++;
else
tj++;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
string str1 = "asddgflsksdjflkdf";
string str2 = "sdflsdzf";
LCS(str1,str2);
return 0;
}
最後更新：2017-04-03 16:49:00