最長公共子序列（動態規劃）

最長公共子序列（動態規劃）

#include
#include
#include
#include
#include
using namespace std;

/*
*最長公共子序列（動態規劃）
*/
vector> c;//c[i][j]記錄串a[0..i]與串b[0..j]之間的最長公共子序列的長度
vector> b;//b[i][j]記錄c[i][j]的值是由哪一個子問題的解得到的

void LCSLength(string m,string n)
{
	//初始化c、b數組
	c = vector>(m.length()+1,vector(n.length()+1,0));//0行0列空余
	b = vector>(m.length()+1,vector(n.length()+1,0));
	
	//構造數組C
	for (unsigned i = 1; i <= m.length() ; i++)
		for (unsigned j = 1; j <= n.length(); j++)
		{
			if(m[i-1]==n[j-1])
			{c[i][j] = c[i-1][j-1]+1;b[i][j] = 1;}
			else
			{
				if (c[i-1][j]>=c[i][j-1])
				{
					c[i][j] = c[i-1][j];b[i][j] = 2;
				}
				else
				{
					c[i][j] = c[i][j-1];b[i][j] = 3;
				}
			}
		}
}

void PrintRes(string m,int i,int j)
{
	if(i == 0 || j == 0) return;
	if(b[i][j] == 1) 
	{
		PrintRes(m,i-1,j-1);
		cout<>a;
	cin>>b;
	//計算最長公共子序列的集合
	LCSLength(a,b);
	cout<<"最長公共子序列為："<