最长公共子序列LCS

20170828_最长公共子序列 LCS

//最长公共子序列LCS
/*
请编写一个函数，输入两个字符串，求它们最长公共子序列。例如：
ABCBDAB和BDCABA，字符序列BCBA和BDAB都是它们的最长公共子序列，则输出4
*/
/*很明显，这是动态规划问题：DP问题
1、假设序列分别是：X=< X0,X1,X2, ... ,Xm-1,Xm >   Y=< Y0,Y1,Y2, ... ,Yn-1,Yn >
它的一个最长公共子序列是：Z=< Z0,Z1,Z2, ... ,Zk >
2、当Xm=Yn时，LCS（Xm，Yn）= LCS（Xm-1，Yn-1）+1
当Xm!=Yn时，LCS（Xm，Yn）= max（LCS（Xm-1，Yn），LCS（Xm，Yn-1））
3、显然，当X或Y为空时，LCS长度是为零。
*/
#include
#include
#include
#include
#include
#include
using namespace std;

class Solution
{
public:
	void GetLCS(const string &strA, const string &strB)
	{
		int n=strA.size();
		int m=strB.size();
		if(n==0 || n==0)
		{
			cout<<0<> dp(n+1,vector(m+1,0));
		//按照状态转移方程，填充表格
		for(int i=1; i<=n; ++i)
		{
			for(int j=1; j<=m; ++j)
			{
				if(strA[i-1]==strB[j-1])
					dp[i][j]=dp[i-1][j-1]+1;
				else
					dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			}
		}
		cout<<>>strA>>strB)
	{
		cout<