c++.txt

动态规划下的最优子序列问题

程序中引入了动态二维数组
#include <iostream>
using namespace std;
const Limit_Size=20;

int main()
{
	int i,j,k,m,n;
	char s1[Limit_Size],s2[Limit_Size],s[Limit_Size];
	cout<<"请输入第一个子序列：";
    cin>>s1;
	m=strlen(s1);
	cout<<"请输入第二个子序列：";
	cin>>s2;
	n=strlen(s2);
	     //为二维数组开辟空间
     int **b = new int*[m+1];
     for ( i = 0;  i < m+1;  i++)
    {
          b[i] = new int[n+1];
    }
	 int **c = new int*[m+1];
     for ( i = 0;  i < m+1;  i++)
    {
          c[i] = new int[n+1];
    }
	for(i=0;i<=m;i++) {c[i][0]=0;b[i][0]=0;}
	for(i=0;i<=n;i++) {c[0][i]=0;b[0][i]=0;}
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
			if(s1[i-1]==s2[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;
			}
//输出c[i][j]
 cout<<'\n';
 for(i=0;i<=m;i++)
 {
  for(j=0;j<=n;j++)
      cout<<c[i][j]<<"  ";
  cout<<'\n';
 }
//输出b[i][j]
 cout<<'\n';
 for(i=0;i<=m;i++)
 {

  for(j=0;j<=n;j++)
      cout<<b[i][j]<<"  ";
  cout<<'\n';
 }
 //输出最长公共子序列
	i=m,j=n,k=0;
	while(i!=0&&j!=0)
	{
		if(b[i][j]==1)
		{
			s[k]=s1[i-1];
			k++;
			i--;
			j--;
		}
		else if(b[i][j]==2)
		        i--;
		else j--;
	}
	cout<<"The LCSLength string: ";
	for(i=k-1;i>=0;i--)
		cout<<s[i];
    cout<<endl;
	//释放二维数组占用的空间
     for ( j = 0; j < m+1; j++)
    {
          delete[] b[j];
    }
	      for ( j = 0; j < m+1; j++)
    {
          delete[] c[j];
    }
    delete[] b;
	delete[] c;
    b = NULL;
	c = NULL;
	return 0;
}